오신, 인류의 희망

//  n       m              
// dp[i][j]   i    j       
//      dp[i][j]=dp[i-1][j-1]+d[i][j-i]
// a. i-1    j-1    j     i    
// b. i     j-i      i          
//    ans=ans+dp[i][n-k*i+i]     n-k*i+i 
//   i        n-k*i+i>=i             

 
#include <iostream>

#include <algorithm>

#include <queue>

#include <stack>

#include <math.h>

#include <stdio.h>

#include <string.h>

using namespace std;

#define MOD 1000000007

#define maxn 1000010

#define maxm 1000010

#define LL long long

int dp[1010][1010];

int main(){

    int i,j;

    dp[0][0]=1;// dp[i][0]=0;

    for(i=1;i<=1000;i++)

    {

        dp[i][i]=1;

        for(j=i+1;j<=1000;j++)

         dp[i][j]=(dp[i-1][j-1]+dp[i][j-i])%MOD;

    }

   // for(i=1;i<=1000;i++)

     // printf("%d ",dp[i][i]);

    int T;

    scanf("%d",&T);

    int m,n,k;

    while(T--){

        scanf("%d %d",&n,&k);

        m=n/k;

        int ans=0;

        for(int i=1;i<=m;i++){

            ans=(ans+dp[i][n-k*i+i])%MOD;

        }

        printf("%d
",ans);

    }

}