Cerința

Avem o funcție F definită pe numere naturale. $F(x)=\{\begin{array}{l}Y,x=0\\ \sum _{i=0}^{x-1}F(i)\end{array}$. Primim Q interogări de tipul st dr, pentru fiecare interogare trebuie să spunem cât este $\sum _{i=st}^{dr}F(i)$ modulo ${10}^9+7$.

Date de intrare

Programul citește de la tastatură numerele Q și Y iar apoi Q perechi de numere st dr.

Date de ieșire

Programul va afișa pe ecran Q linii, pe linia i se află răspunsul pentru a i întrebare (în ordinea citirii).

Restricții și precizări

• 1 ≤ Q ≤ 100.000
• 0 ≤ st ≤ dr ≤ 1.000.000.000
• 1 ≤ Y ≤ 1.000.000.000

Exemplu:

Intrare

2 3
0 2
2 4

Ieșire

12
42

Explicație

. x: 0 1 2 3 4 ...
F(x): 3 3 6 12 24 ...