问题1007--牛吃花

1007: 牛吃花

时间限制: 1 Sec  内存限制: 128 MB
提交: 137  解决: 56
[提交] [状态] [讨论版] [命题人:]

题目描述

BSNY养了一头怪牛,喜欢吃红色和白色的花,于是BSNY在一条直线上养了n朵花,不是红色就是白色。这头牛还有其他怪的地方,喜欢从头往尾吃下去,并且白色的花需要连续k朵才一口吃进,不然就不吃了。所以这让BSNY很苦恼,除了花的颜色是红白外,还要考虑花的位置。

比如有3盆花,k=2,那么WRR(W表示白花,R表示红花),牛不会吃,因为连续的白花才一朵,WWW,牛也不会吃,因为吃了一口后,只剩下W了,剩下一朵牛也不要吃了。所以可行的方案为: RRR, RWW, WWR

现在问你,当牛想吃花的数量为[ai, bi]时,有多少种可行的方案

输入

输入tkt表示有多少询问,k如题描述

接下来t行,每行输入ai, bi,表示询问当牛要吃[ai, bi]朵花时,有多少种可行的方案

输出

输出t行,每行相应答案

答案可能为很大,所以输出的答案需要mod 1000000007

样例输入 Copy

3 2
1 3
2 3
4 4

样例输出 Copy

6
5
5

提示

k=2, n=1时,方案可以是R

k=2, n=2时,方案可以是RRWW

k=2, n=3时,方案可以是RRR, RWWWWR

k=2, n=4时,方案可以是RRRR, RWWR, WWRR, RRWW, WWWW

所以,当问[1, 3]时,有1+2+3=6种方案

[2, 3]时,有2+3=5种方案

[4, 4]时,有5种方案

 

【数据规模和约定】

1<= t, k <= 10^5

1<= ai <=bi <= 10^5

来源/分类