Cerința

Avem o funcție F definită pe numere naturale. \(F(x) = \begin{cases} Y, x = 0 \\ \sum_{i=0}^{x-1} F(i) \end{cases}\). 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 ...