#include
using namespace std;
long long rem=1000000000+7;
int tilling(int n,int m){
if(n<m){
return 1;
}
return (tilling(n-1,m)%rem +tilling(n-m,m)%rem)%rem;
}
int main() {
int t;
cin>>t;
while(t–){
int n,m;
cin>>n>>m;
cout<<tilling(n,m)%rem<<endl;
}
return 0;
}