D.Flowers

D.Flowers

time limit per test: 1.5 secondsmemory limit per test: 256 megabytes
每次测试的时限：1.5秒每次测试的时限：256兆字节

input: standard input
输入：标准输入

output: standard output
产出：标准产出

We saw the little game Mamot made for Mole’s lunch.Now it’s Mamot’s diner time and, as we all .now,Marmot eats flowers.At everydinner he eats some red and white flowers. Therefore a dinner can be represented as a sequence of several flowers, some of them whiteand some of them red.
我们看到了马莫为鼹鼠的午餐做的小游戏。现在是马莫特的就餐时间，就像我们大家一样。现在，土拨鼠吃花。在每一顿晚餐，他都吃一些红白相间的花。因此，晚餐可以表示成几朵花的顺序，有些是白色的，有些是红色的。

But, for a dinner to be tasty, there is a rule: Marmot wants to eat white flowers only in groups of size k.
但是，要想让晚餐变得美味，有一条规则：土拨鼠只想吃白色的花，成群的大小为k。

Now Marmot wonders in how many ways he can eat between a and b flowers.As the number of ways could be very large, print it modulo1000000007 (109+7).
现在Marmot想知道他能在a和b花之间吃多少种食物，因为它的数量可能很大，所以打印modulo10000007(109+7)。

lnput
输入

Input contains several test cases.
Input contains several test cases.

The first line contains two integers t and k(1<t,k<10’), where t represents the number of test cases.The next t lines contain two integers a; and b; (1≤a≤bi≤10’), describing the i-th test.
第一行包含两个整数t和k(1<t，k<10‘)，其中t表示测试用例的数目，下一行包含两个整数a；和b；(1≤a≤bi≤10’)，描述第一次测试。

线性dp，前缀数组加速

long long a[100007],b[100007];
int main()
{
	int t, k;
	b[0] = 0,a[0]=1;
	cin >> t >> k;
	if (k > 1)
		b[1]=a[1] = 1;
	else
		b[1]=a[1] = 2;
	for (int i = 2; i < 100001; ++i)
	{
		if (i >= k)
			a[i] =( a[i - 1] + a[i - k])% 1000000007;
		else
			a[i] = 1;
	}
	for (int i = 2; i < 100001; ++i)
		b[i] = (a[i] + b[i-1])% 1000000007;
	while (t--)
	{
		int x, y;
		cin >> x >> y;
		cout << (b[y] - b[x-1] + 1000000007) % 1000000007 << endl;
	}
	return 0;
}