Description

 给出正整数n,k，要求使正整数n拆分成若干个正整数的和，并且使得拆分后的数中相同的数的出现次数小于k次。

 

Input

 第一行输入T,共有T组测试样例，接下来2~T+1行，每行输入n,k。 1<=n,k,T<=10^5

 

Output

 输出T行，每行对应的拆分方案，最后答案取模1e9+7

 

Sample Input

4
4 2
4 3
4 4
4 5

Sample Output

2
4
4
5

HINT

 

 n=4,k=2时，可拆分成4=4,4=1+3

 

n=4,k=3时，可拆分成4=1+2+1,4=2+2,4=1+3,4=4

#include<bits/stdc++.h>

using namespace std;

typedef long long  ll;

const int MOD=1e9+7;
const int MAXN=1e6+10;

ll p[MAXN];

void init(){
    p[0]=1;
    for(ll i=1;i<=100000;i++){
        for(ll j=1,w=1;w<=i;j++,w=(3*j*j+j)/2)
            if(j&1) p[i]=(p[i]+p[i-w])%MOD;
            else    p[i]=((p[i]-p[i-w])%MOD+MOD)%MOD;
        for(ll j=1,w=2;w<=i;j++,w=(3*j*j-j)/2)
            if(j&1) p[i]=(p[i]+p[i-w])%MOD;
            else    p[i]=((p[i]-p[i-w])%MOD+MOD)%MOD;
    }
}

ll solve(ll n,ll k){
    ll ans=p[n];
    for(ll j=1,w=k;w<=n;j++,w=k*(3*j*j+j)/2)
        if(j&1) ans=((ans-p[n-w])%MOD+MOD)%MOD;
        else    ans=(ans+p[n-w])%MOD;
    for(ll j=1,w=2*k;w<=n;j++,w=k*(3*j*j-j)/2)
        if(j&1) ans=((ans-p[n-w])%MOD+MOD)%MOD;
        else    ans=(ans+p[n-w])%MOD;
    return ans;
}

int main(void)
{
    init();
    int T;  cin>>T;
    while(T--){
        ll n,k;   scanf("%lld%lld",&n,&k);
        printf("%lld\n",solve(n,k));
    }
    return 0;
}