There are $n$ coins arranged in a row. On the $i^{th}$ coin, there is number $A_i$ written on the head face and $B_i$ written on the tail face.
Let's denote function $f(l, r)$ as the maximum possible sum of coins $l, l + 1, ...,r$ that is not divisible by $k$. You
can flip the coin as you wish. If there is no way to flip the coins then $f(l, r)=0$.
Calculate:
$$
\sum_{l=1}^{n} \sum_{r=l}^{n} f(l, r)
$$
### Input
- The first line contains two integers $n, k$.
- The next $n$ lines, the $i^{th}$ line contains two integers $A_i, B_i$.
### Output
- Print the result, modulo $10^9+7$.
### Constraints
- $1 \le n \le 10^5$.
- $1 \le A_i, B_i,k \le 10^9$.
### Example
Input:
```
3 3
1 2
2 3
3 1
```
Output:
```
23
```
