Задача №114964. День рождения
Богдан получил на день рождения настольную игру «Сумма на подотрезке». Эта увлекательная настольная игра состоит из \(n\) двусторонних карточек. На каждой сторонах карточки написано некоторое целое число. Карточки выкладываются в ряд на стол и получают номера с 1 до \(n\) слева направо. После этого карточки можно переворачивать, но нельзя менять местами.
Игрок в качестве задания получает номера \(l\) и \(r\), а затем каждую карточку между \(l\)-й и \(r\)-й включительно размещает одной из сторон наверх. Цель игрока — добиться, чтобы сумма чисел на верхних сторонах карточек от \(l\)-й и \(r\)-й включительно оказалась максимальной.
Богдану быстро наскучило просто искать максимальную сумму, и он решил усложнить игру. Теперь Богдан выбирает число \(k\), при выполнении задания для карточек от \(l\)-й и \(r\)-й включительно он переворачивает карточки таким образом, что получившаяся сумма чисел была максимальной, но не делилась на \(k\). Если Богдан выполняет задание с карточками от \(l\)-й до \(r\)-й, то полученную сумму он обозначает как \(f(l, r)\). Если от \(l\) до \(r\) невозможно выбрать числа на карточках так, чтобы полученная сумма была не кратна \(k\), Богдан считает, что \(f(l,r)=0\).
Наигравшись с карточками, Богдан задумался над такой задачей. Он захотел посчитать сумму всех \(f(l, r)\) для всех возможных пар \(l\) и \(r\), то есть найти \(\sum\limits_{1 \le l \le r \le n}f(l,r)\).
Помогите Богдану найти эту сумму. Так как ответ может быть очень большим, вычислите его по модулю \(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\).
3 3 1 2 2 3 3 1
23
5 5 4 1 4 2 2 3 2 4 1 5
130