markdown

D. 花朵

我们见过小游戏“Marmot 为 Mole 的午餐准备的游戏”。现在是 Marmot 的晚餐时间，众所周知，Marmot 吃花朵。每顿晚餐他都会吃一些红色和白色的花朵。因此，一顿晚餐可以表示为一个由若干花朵组成的序列，其中一些是白色的，一些是红色的。

但是，为了让晚餐美味，有一条规则：Marmot 希望只以大小为 $k$ 的组的形式吃白色花朵。

现在 Marmot 想知道，在吃 $a$ 到 $b$ 朵花之间（包含两端）有多少种不同的方式。由于方式数量可能非常大，请输出结果对 $1000000007$（$10^9 + 7$）取模后的值。

输入

输入包含多个测试用例。

第一行包含两个整数 $t$ 和 $k$（$1 \le t, k \le 10^5$），其中 $t$ 表示测试用例的数量。

接下来的 $t$ 行，每行包含两个整数 $a_i$ 和 $b_i$（$1 \le a_i \le b_i \le 10^5$），描述第 $i$ 个测试用例。

输出

输出 $t$ 行到标准输出。第 $i$ 行应包含 Marmot 在晚餐时吃 $a_i$ 到 $b_i$ 朵花之间的方式总数对 $1000000007$（$10^9 + 7$）取模后的结果。

样例

输入

3 2
1 3
2 3
4 4

输出

6
5
5

注释

• 对于 $K = 2$ 且长度为 $1$，Marmot 可以吃 (R)。
• 对于 $K = 2$ 且长度为 $2$，Marmot 可以吃 (RR) 和 (WW)。
• 对于 $K = 2$ 且长度为 $3$，Marmot 可以吃 (RRR)、(RWW) 和 (WWR)。
• 对于 $K = 2$ 且长度为 $4$，Marmot 可以吃例如 (WWWW) 或 (RWWR)，但不能吃例如 (WWWR)。