← 返回题目列表

Codeforces · 474/D

D. 鲜花

中文机器翻译题面 查看原题

我们看到了土拨鼠为鼹鼠的午餐做的小游戏。现在是土拨鼠的晚餐时间,众所周知,土拨鼠吃花。每次晚餐他都会吃一些红花和白花。因此,一顿晚餐可以表示为一系列的几朵花,其中一些是白色的,一些是红色的。

但是,为了让晚餐变得美味,有一条规则:土拨鼠只想吃大小为 k 的白花。

现在土拨鼠想知道在 a 和 b 朵花之间他可以用多少种方式吃东西。由于路数可能非常大,因此打印它对 1000000007 (109 + 7) 取模。

输入

输入包含多个测试用例。

第一行包含两个整数 t 和 k (1 ≤ t, k ≤ 105),其中 t 表示测试用例的数量。

接下来的 t 行包含两个整数 ai 和 bi (1 ≤ ai ≤ bi ≤ 105),描述第 i 个测试。

输出

将 t 行打印到标准输出。第 i 行应包含 Marmot 在晚餐时在 ai 和 bi 花之间吃东西的方式数量,模 1000000007 (109 + 7)。

示例

输入 #1

3 2
1 3
2 3
4 4

输出 #1

6
5
5

注意

- 对于 K = 2 且长度为 1 的土拨鼠可以吃 (R)。
- 对于 K = 2 且长度为 2 的土拨鼠可以吃 (RR) 和 (WW)。
- 对于 K = 2 且长度为 3 的土拨鼠可以吃 (RRR)、(RWW) 和 (WWR)。
- 对于 K = 2 且长度为 4,Marmot 可以吃,例如 (WWWW) 或 (RWWR),但例如他不能吃 (WWWR)。