Bogdan 收到了一份生日礼物：一个名为“子段和”的桌游。这个有趣的游戏包含 $n$ 张双面卡片。每张卡片的每一面都写有一个整数。这些卡片按行排列在桌面上，从左到右编号为 $1$ 到 $n$。排列好后，卡片可以翻面，但不能交换位置。

玩家会收到任务，每个任务是一对数字 $l$ 和 $r$。收到任务后，玩家将编号从 $l$ 到 $r$（包含 $l$ 和 $r$）的每张卡片以某一面上翻。目标是使编号从 $l$ 到 $r$ 的卡片上侧数字之和尽可能大。

Bogdan 对追求最大和感到厌倦，于是他决定增加游戏难度。现在 Bogdan 选择了一个数字 $k$，当他解决编号从 $l$ 到 $r$ 的卡片任务时，他会将这些卡片以某种方式翻面，使得它们上侧数字之和尽可能大，且不能被 $k$ 整除。如果 Bogdan 能够完成这个任务，他将得到的最大和记为 $f(l, r)$。如果他无法选择翻面方式使得上侧数字之和不能被 $k$ 整除，他认为 $f(l, r) = 0$。

玩了一会儿后，Bogdan 开始思考以下问题。他想要计算所有可能的 $l$ 和 $r$ 对的 $f(l, r)$ 之和，换句话说，计算 $\sum_{1 \le l \le r \le n} f(l, r)$。

请帮助 Bogdan 计算这个总和。由于答案可能非常大，请将其对 $10^9 + 7$ 取模。

输入格式

第一行包含两个整数 $n$ 和 $k$ ($1 \le n \le 5 \cdot 10^5$; $1 \le k \le 10^9$)。

接下来的 $n$ 行，每行包含一张桌面上卡片的描述：两个整数 $a_i$ 和 $b_i$ ($1 \le a_i, b_i \le 10^9$)，分别表示编号为 $i$ 的卡片两面上的数字。

输出格式

输出一个整数，即答案对 $10^9 + 7$ 取模的结果。

样例

样例输入 1

3 3
1 2
2 3
3 1

样例输出 1

23

样例输入 2

5 5
4 1
4 2
2 3
2 4
1 5

样例输出 2

130