题目描述

在一个图书馆整理活动中，管理员需要将两种颜色的书籍（红色和蓝色）排列在书架上。规则如下：

    1.蓝色书籍每次必须连续摆放恰好 k 本。

    2.红色书籍每次可以单独摆放，也可以连续摆放任意数量。

管理员需要计算书架长度在 [l, r] 范围内的所有合法排列方案数，结果对10^9+7 取模。

输入格式

第一行包含两个整数 t 和 k（1 ≤ t ≤ 1e5，1 ≤ k ≤ 1e5），表示测试用例数量和每组蓝色书籍的固定长度。

接下来 t 行，每行包含两个整数 l 和 r（1 ≤ l ≤ r ≤ 1e6），表示查询的区间。

输出格式

对于每个查询，输出一个整数，表示合法方案数模 10^9+7 的结果。

输入/输出例子1

3 2
1 3
2 3
4 4

6
5
5

样例解释

样例解释

当 k=2 时：

长度为 1 时，只能是红色书籍（1 种）。

长度为 2 时，可能是 RR 或 BB（2 种）。

长度为 3 时，可能的组合有 RRR、RBB、BBR（3 种），总共有 1+2+3=6 种。

数据范围

50% 数据 t<=100,1 ≤ l ≤ r ≤ 1e5

100% 数据 t<=1000000,1 ≤ l ≤ r≤ 1e6