생일

보그단은 생일 선물로 "Subsegment sum"이라는 보드게임을 받았다. 이 게임은 양면 카드 $n$장으로 이루어져 있다. 각 카드의 양면에는 정수가 하나씩 적혀 있다. 카드는 테이블 위에 왼쪽에서 오른쪽으로 한 줄로 놓이며, 왼쪽부터 1번에서 $n$번까지 번호가 붙는다. 카드를 놓은 뒤에는 뒤집을 수 있지만, 자리를 바꿀 수는 없다.

플레이어는 과제를 받는다. 과제는 두 수 $l$과 $r$의 쌍이다. 과제를 받으면 플레이어는 번호가 $l$부터 $r$까지인 카드를 각각 한쪽 면이 위로 향하도록 놓는다. 목표는 $l$번부터 $r$번까지 카드의 윗면 수의 합을 최대로 만드는 것이다.

보그단은 최대 합을 구하는 것만으로는 재미가 없어서 게임을 더 어렵게 만들었다. 그는 수 $k$를 정한다. $l$번부터 $r$번까지 카드의 과제를 풀 때, 윗면 수의 합이 $k$로 나누어떨어지지 않으면서 가능한 한 크도록 카드의 면을 정한다. 그런 합을 만들 수 있으면 그 최대 합을 $f(l, r)$이라고 한다. 합이 $k$로 나누어떨어지지 않도록 면을 고를 수 없으면 $f(l,r)=0$이다.

보그단은 모든 쌍 $l$, $r$에 대해 $f(l, r)$을 더한 값, 즉 $\sum_{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$로 나눈 나머지를 정수 하나로 출력한다.