Description
现在是土拨鼠的晚餐时间，我们都知道，土拨鼠吃花。每顿饭他都吃一些红花和白花。因此一顿晚餐可以被描绘成几朵鲜花的序列，其中一些是白色的，另一些是红色的。
为了使晚餐变得有滋有味，土拨鼠有一个规则：1.他一次只能吃1朵红花，2.一次只能吃k朵白花。
现在土拨鼠想知道有多少种方法能让他吃掉a朵花到b朵花。由于方法的数量也许会非常大，输出时取余1000000007(10^9 + 7)。
Input
输入包含几组测试样例。 第一行包括两个整数t和k(1 ≤ t, k ≤ 10^5)，t代表测试样例的个数，k为一次只想吃k个白花。
接下来的t行，每行包含两个整数ai和bi(1 ≤ ai ≤ bi ≤ 10^5)，描述第i个测试样例。
Output
输出t行。第i行包含土拔鼠能吃掉ai朵花到bi朵花之间的方法总数（取余1000000007 (10^9 + 7））