#include<bits/stdc++.h>
#define ll long long
#define Mod 1000000007
using namespace std;
ll countWaysUtil(ll n, ll m) 
{ 
    int res[n]; 
    res[0] = 1; res[1] = 1; 
    for (int i=2; i<=n; i++) 
    { 
       res[i] = 0; 
       for (int j=1; j<=m && j<=i; j++) 
         res[i] += res[i-j] % Mod; 
    } 
    return res[n-1] % Mod; 
} 
ll countWays(ll s, ll m) 
{ 
    return countWaysUtil(s+1, m) % Mod;
} 
int main () 
{ 
    int t; cin >> t;
	while(t--){
		ll s, m;
		cin >> s >> m;
		cout << countWays(s,m) << endl;
	} 
    return 0; 
}