CF474D.Flowers

We saw the little game Marmot made for Mole's lunch. Now it's Marmot's dinner time and, as we all know, Marmot eats flowers. At every dinner he eats some red and white flowers. Therefore a dinner can be represented as a sequence of several flowers, some of them white and some of them red.

But, for a dinner to be tasty, there is a rule: Marmot wants to eat white flowers only in groups of size k.

Now Marmot wonders in how many ways he can eat between a and b flowers. As the number of ways could be very large, print it modulo 1000000007 (109 + 7).

我们曾见过土拨鼠为鼹鼠的午餐设计的小游戏。现在到了土拨鼠的晚餐时间，众所周知，土拨鼠吃花。每顿晚餐，他都会吃一些红花和白花。因此，一顿晚餐可以表示为一个由若干花朵组成的序列，其中一些是白花，另一些是红花。

但要让一顿晚餐变得美味，需满足一条规则：土拨鼠只允许以大小恰好为 $k$ 的组来吃白花。

现在土拨鼠想知道：他一共能在 $a$ 到 $b$ 朵花（含端点）之间有多少种不同的吃法？由于方案数可能非常大，请将结果对 $1000000007$（即 $10^9 + 7$）取模后输出。

Input contains several test cases.

The first line contains two integers t and k (1 ≤ t, k ≤ 105), where t represents the number of test cases.

The next t lines contain two integers a__i and b__i (1 ≤ a__i ≤ b__i ≤ 105), describing the i-th test.

输入包含多个测试用例。

第一行包含两个整数 $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$ 个测试用例。

Print t lines to the standard output. The i-th line should contain the number of ways in which Marmot can eat between a__i and b__i flowers at dinner modulo 1000000007 (109 + 7).

向标准输出打印 t 行。第 i 行应包含土拨鼠在晚餐时吃掉介于 a__i 与 b__i 朵花之间的方案数，结果对 1000000007（即 $10^9 + 7$）取模。

• For K = 2 and length 1 Marmot can eat (R).

• For K = 2 and length 2 Marmot can eat (RR) and (WW).

• For K = 2 and length 3 Marmot can eat (RRR), (RWW) and (WWR).

• For K = 2 and length 4 Marmot can eat, for example, (WWWW) or (RWWR), but for example he can't eat (WWWR).

• 当 $K = 2$ 且长度为 1 时，土拨鼠可以吃（R）。

• 当 $K = 2$ 且长度为 2 时，土拨鼠可以吃（RR）和（WW）。

• 当 $K = 2$ 且长度为 3 时，土拨鼠可以吃（RRR）、（RWW）和（WWR）。

• 当 $K = 2$ 且长度为 4 时，土拨鼠可以吃，例如（WWWW）或（RWWR），但例如不能吃（WWWR）。