Flowers

 

话说某个幸运的小伙伴X拿到了kevin女神送的蛋糕，然而他的吃法非常奇特，他独创了两种吃蛋糕的办法：一、一次吃一整个蛋糕；二、一次吃k个蛋糕。

那么，当蛋糕数量为x1到x2之间时，一共能有几种不同的吃法呢？

由于答案很大，输出结果mod 1000000007的值

Input

第一行有两个正整数t,k(1<=t,k<=100000) ，其中t表示数据的组数。

接下来t行，每行两个数x1, x2(1<=x1<=x2<=100000)。

Output

共t行，每行一个正整数x，表示蛋糕数量在x1-x2之间时，一共能有几种不同的吃法，结果对(10^9+7)取模

Sample Input

3 2

1 3

2 3

4 4

Sample Output

6

5

5

Hint

样例中，k=2

我们标记吃法1为A，吃法2为B

当蛋糕数为1时，共1种吃法 即为A

当蛋糕数为2时，共2种，分别为 AA,B

当蛋糕数为3时，共3种，分别为 AAA,AB,BA

当蛋糕数为4时，共5种，分别为 AAAA, AAB,ABA,BAA,BB

 

sol：开始以为是组合数一样的东西，搞了一会后严重自闭，发现是dp。。。

dp[i]表示蛋糕数量为 i 的吃法，对dp记个前缀和就可以O(1)查询了

#include 
       
        using namespace std;typedef long long ll;inline ll read(){    ll s=0;    bool f=0;    char ch=' ';    while(!isdigit(ch))    {        f|=(ch=='-'); ch=getchar();    }    while(isdigit(ch))    {        s=(s<<3)+(s<<1)+(ch^48); ch=getchar();    }    return (f)?(-s):(s);}#define R(x) x=read()inline void write(ll x){    if(x<0)    {        putchar('-'); x=-x;    }    if(x<10)    {        putchar(x+'0'); return;    }    write(x/10);    putchar((x%10)+'0');    return;}#define W(x) write(x),putchar(' ')#define Wl(x) write(x),putchar('\n')const ll Mod=1000000007;const int N=100005;int T;ll K;ll Qzh[N];ll dp[N];int main(){    int i,j;    R(T); R(K);    dp[0]=Qzh[0]=1;    for(i=1;i<=100000;i++)    {        dp[i]+=dp[i-1];        if(i>=K) dp[i]+=dp[i-K];        dp[i]-=(dp[i]>=Mod)?Mod:0;        Qzh[i]=Qzh[i-1]+dp[i];        Qzh[i]-=(Qzh[i]>=Mod)?Mod:0;    }    while(T--)    {        int l=read(),r=read();        Wl((Qzh[r]-Qzh[l-1]+Mod)%Mod);    }    return 0;}/*input3 21 32 34 4output655*/