D. Цветы
ограничение по времени на тест
1.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Мы видели маленькую игру, которую Сурок приготовил для Крота на обед. Теперь Сурку пора ужинать — а мы все знаем, что Сурок ест цветы. За каждым ужином он ест немного красных и немного белых цветов. Таким образом, ужин можно представить как последовательность белых и красных цветов.

Но для того, чтобы ужин был вкусный, есть одно правило: когда Сурок хочет отведать белых цветов, он потребляет их только группами размера k.

Теперь Сурку интересно, сколько существует способов съесть от a до b цветов по его правилам. Так как количество способов может быть очень большим, выведите его по модулю 1000000007 (109 + 7).

Входные данные

На вход подаётся несколько наборов входных данных.

В первой строке записано два целых числа t и k (1 ≤ t, k ≤ 105), где t обозначает количество тестовых примеров.

В следующих t строках записано по два целых числа ai и bi (1 ≤ ai ≤ bi ≤ 105), описывающих i-й тест.

Выходные данные

Выведите t строк. В i-й строке должно содержаться количество способов, которыми Сурок может съесть от ai до bi цветков за ужином, взятое по модулю 1000000007 (109 + 7).

Примеры
Входные данные
3 2
1 3
2 3
4 4
Выходные данные
6
5
5
Примечание
  • При K = 2 и длине 1 Сурок может съесть (R).
  • При K = 2 и длине 2 Сурок может съесть (RR) и (WW).
  • При K = 2 и длине 3 Сурок может съесть (RRR), (RWW) и (WWR).
  • При K = 2 и длине 4 Сурок может съесть, например, (WWWW) или (RWWR). Но вот (WWWR), к примеру, съесть но не может.