24866번 - Birthday 다국어

문제

Bogdan received a birthday gift: a board game called "Subsegment sum". This entertaining game consists of $n$ two-sided cards. An integer is written on each side of each card. The cards are arranged in a row on the table and are indexed from 1 to $n,ドル left to right. After the arrangement the cards can be turned over, but not swapped.

The player receives tasks, each task is a pair of numbers $l$ and $r$. After receiving a task, the player places each card with index from $l$ to $r,ドル inclusive, some side up. The target is to make the sum of the numbers on the upper sides of cards with index from $l$ to $r,ドル inclusive, as large as possible.

Bogdan became bored with achieving maximum sums, so he decided to make the game harder. Now Bogdan selects a number $k,ドル and when he solves the task for cards from $l$ to $r,ドル inclusive, he places these cards with some side up in such a way that the sum of the numbers on their upper sides was as large as possible, but not divisible by $k$. If Bogdan is able to solve this task, he denotes the received maximum sum as $f(l, r)$. If he is unable to select sides to make the sum on the upper sides indivisible by $k,ドル he considers $f(l,r)=0$.

After some playing, Bogdan started thinking about the following problem. He wants to calculate the sum of $f(l, r)$ for all possible pairs $l$ and $r,ドル in other words, calculate $\sum\limits_{1 \le l \le r \le n}f(l,r)$.

Help Bogdan find this sum. Since the answer can be very large, calculate it by modulo 10ドル^9+ 7$.

입력

The first line contains two integers $n$ and $k$ (1ドル \le n \le 5 \cdot 10^5$; 1ドル \le k \le 10^9$).

Each of the next $n$ lines contains a description of a card on the table: two integers $a_i$ and $b_i$ (1ドル \le a_i, b_i \le 10^9$) --- the numbers written on two sides of the card with index $i$.

출력

Output one integer, the answer taken modulo 10ドル^9+7$.

제한

힌트