题目描述

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

一次任务由一对数 $l,r$ 给出。玩家需要把编号从 $l$ 到 $r$ 的卡片各选择一面朝上，使这些朝上数字之和尽可能大。

Bogdan 玩腻了普通最大化，于是增加了难度。他先选定一个数 $k$。对于区间 $[l,r]$，他要在使朝上数字之和尽可能大的同时，要求这个和不能被 $k$ 整除。如果能做到，记这个最大和为 $f(l,r)$；如果无法选择卡片使和不被 $k$ 整除，则定义 $f(l,r)=0$。

Bogdan 想计算所有可能区间的 $f(l,r)$ 之和：

由于答案可能很大，请输出其对 $10^9+7$ 取模后的结果。

输入格式

第一行包含两个整数 $n,k$。

接下来 $n$ 行，每行包含两个整数 $a_i,b_i$，表示第 $i$ 张卡片两面写着的数。

输出格式

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

数据范围

$1 \le n \le 5\cdot 10^5$，$1 \le k \le 10^9$，$1 \le a_i,b_i \le 10^9$。

样例 1

输入：
3 3
1 2
2 3
3 1

输出：
23

样例 2

输入：
5 5
4 1
4 2
2 3
2 4
1 5

输出：
130