题目描述

兔子和乌龟进行赛跑。

兔子每秒能跑 $k$ 米，但如果走每秒只能走 $1$ 。

兔子比较懒，它不会连续两秒都进行跑。

已知兔子最终一共移动距离范围为 L 到 R 米。你想知道兔子多少种不同的移动方法。

当且仅当两种方法移动的距离不同，或花费的时间不同，或在一秒钟内，其中一种方法是走，另一种方法是跑时，它们才是不同的。

输入描述

第一行输入包含两个整数 Q 和 k。Q 是查询次数（Q<=100000,2<=k<=100000）

接下来的 Q 行，每行包含两个整数 L 和 R。

输出描述

对于每个查询，打印一行，其中包含一个整数，表示查询答案的模数为 1000000007。

样例

样例输入#1

3 3
3 3
1 4
1 5

样例输出#1

2
7
11