Мы видели маленькую игру, которую Сурок приготовил для Крота на обед. Теперь Сурку пора ужинать — а мы все знаем, что Сурок ест цветы. За каждым ужином он ест немного красных и немного белых цветов. Таким образом, ужин можно представить как последовательность белых и красных цветов.
Но для того, чтобы ужин был вкусный, есть одно правило: когда Сурок хочет отведать белых цветов, он потребляет их только группами размера k.
Теперь Сурку интересно, сколько существует способов съесть от a до b цветов по его правилам. Так как количество способов может быть очень большим, выведите его по модулю 1000000007 (109 + 7).
Выходные данные
Выведите t строк. В i-й строке должно содержаться количество способов, которыми Сурок может съесть от ai до bi цветков за ужином, взятое по модулю 1000000007 (109 + 7).
Примечание
- При K = 2 и длине 1 Сурок может съесть (R).
- При K = 2 и длине 2 Сурок может съесть (RR) и (WW).
- При K = 2 и длине 3 Сурок может съесть (RRR), (RWW) и (WWR).
- При K = 2 и длине 4 Сурок может съесть, например, (WWWW) или (RWWR). Но вот (WWWR), к примеру, съесть но не может.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 2
1 3
2 3
4 4
|
6
5
5
|