现在是土拨鼠的晚餐时间啦！众所周知，土拨鼠吃喜欢的食物：花，每次晚饭他都吃一些红花和白花。因此，晚餐可以表示为几朵花的序列，一些是白色的，一些是红色的。
但是，为了让晚餐变得美味，土拨鼠有一条规则：土拨鼠只想吃数量为k朵的白花（ groups of size k）。
现在，土拨鼠想知道，如果他的晚餐最小可以吃a朵话，最多可以吃b多花，他能有多少种方法吃花。由于方式的数量可能非常大，所以结果对1000000007（10^9+7）取模后输出。
题目翻译不太好，可以看原题:https://codeforces.com/problemset/problem/474/D
输入包含几个测试用例。
第一行包含两个整数t和k（1≤t, k≤10^5），其中t表示测试用例的数量。
接下来的t行包含两个整数ai和bi（1≤ai≤bi≤10^5）描述了第i次测试。
输出t行数据，第i行应该包含土拨鼠在晚餐中吃ai至bi朵花的可能方法数，模数为1000000007（10^9+7）。
输入样例：
3 2 1 3 2 3 4 4
6 5 5
提示：
对于K=2和长度1，土拨鼠可以吃（R）。
对于K=2和长度2，土拨鼠可以吃（RR）和（WW）。
对于K=2和长度3，土拨鼠可以吃（RRR）、（RWW）和（WWR）。
对于K=2和长度4，土拨鼠可以吃，例如，（WWWW）或（RWWR），例如，他不能吃（WWWR）。
3 2
1 3
2 3
4 46
5
5