// this is my code for tilling problem II . but it is not working can u tell me the error ?
#include<bits/stdc++.h>
//#include<ext/pb_ds/assoc_container.hpp> // Common file
//#include<ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
#define int long long
#define pb push_back
#define ff first
#define ss second
#define eb emplace_back
#define vi vector
#define vii vector<vector>
#define pr pair<int,int>
#define ump unordered_map<int,bool>
#define mp map<int,list>
#define endl “\n”
#define sz(x) (int)(x).size()
#define trace(x) cerr<<#x<<": “<<x<<” "<<endl;
#define all© ©.begin(), ©.end()
const int MOD = 1e9 + 7 ;
const int INF = 0x3f3f3f3f; // LLONG_MAX PE OVERFLOW TOH YE USE KAR.
using namespace std;
//using namespace __gnu_pbds;
//typedef tree<int, null_type, less, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
int n,m;
int solve(int i){
if(i == 0 or (i-m) < 0) return 1;
return (solve(i-1)%MOD + solve(i-m)%MOD)%MOD;
}
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
//freopen("addin.txt","r",stdin);
//freopen("addout.txt","w",stdout);
int t;
cin >> t;
while(t--){
cin >> n >> m;
cout<<solve(n)<<endl;
}
return 0;
}
// CHECK FOR CORNER CASES LIKE 0,1 etc.
// READ
// THINK
// CODE
// DEBUG
// AC