花朵

• 时间限制：1.5 秒
• 内存限制：256 MiB

题目描述

一顿晚餐可以表示为一列红花和白花。红花可以单独出现；白花则必须按连续恰好 $k$ 朵为一组出现。换言之，一个合法序列可以由若干个“单朵红花”和“连续 $k$ 朵白花”的块依次拼接而成，不同的块顺序视为不同方案。

给定 $t$ 个询问。对每个区间 $[a_i,b_i]$，求长度为 $a_i,a_i+1,\ldots,b_i$ 的所有合法序列数量之和。答案对 $10^9+7$ 取模。

输入格式

第一行包含两个整数 $t,k$。

接下来 $t$ 行，每行包含两个整数 $a_i,b_i$。

输出格式

对每个询问输出一行，表示对应区间的方案总数对 $10^9+7$ 取模后的值。

样例输入 1

3 2
1 3
2 3
4 4

样例输出 1

6
5
5

数据范围

$1\le t,k\le10^5$，$1\le a_i\le b_i\le10^5$。