我们已经看过了旱獭为鼹鼠午餐准备的小游戏。现在轮到旱獭的晚餐时间了，众所周知，旱獭喜欢吃花。在每顿晚餐时，他会吃一些红花和一些白花。因此，一顿晚餐可以表示为一串若干花朵序列，其中有些是白花，有些是红花。

但是，为了让晚餐变得美味，有一个规则：旱獭只想以每组 $k$ 朵的形式吃白花。

现在，旱獭想知道，他能以多少种方式吃下 $a$ 到 $b$ 朵花。由于方案总数可能非常大，请输出结果对 $1000000007$（$10^{9}+7$）取模后的值。

输入格式

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

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

输出格式

打印 $t$ 行到标准输出。第 $i$ 行应该包含土拨鼠晚餐吃 $a_i$ 到 $b_i$ 朵花的方式数对 $1000000007$（$10^9 + 7$ ）取模后的值。

3 2
1 3
2 3
4 4

6
5
5

2 3
42 42
17 46

5736961
83315513

3 8
28 37
38 41
50 50

4522
6748
14674

说明/提示

• 当 $k=2$ 且长度为 $1$ 时，旱獭只能吃（$R$）。
• 当 $k=2$ 且长度为 $2$ 时，旱獭可以吃（$RR$）和（$WW$）。
• 当 $k=2$ 且长度为 $3$ 时，旱獭可以吃（$RRR$）、（$RWW$）和（$WWR$）。
• 当 $k=2$ 且长度为 $4$ 时，旱獭可以吃例如（$WWWW$）或（$RWWR$），但不能吃（$WWWR$）。