我们看到了土拨鼠为鼹鼠的午餐做的小游戏。现在是土拨鼠的晚餐时间,众所周知,土拨鼠吃花。每次晚餐他都会吃一些红花和白花。因此,一顿晚餐可以表示为一系列的几朵花,其中一些是白色的,一些是红色的。
但是,为了让晚餐变得美味,有一条规则:土拨鼠只想吃大小为 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)。