#include<iostream>#include<cstring>#include<algorithm>#include<string>#include<cstdio>using namespace std;#define MAX_SIZE 32struct Matrix{ int size; long long modulo; long long element[MAX_SIZE][MAX_SIZE]; void setSize(int); void setModulo(long long); Matrix operator* (Matrix); Matrix power(int);};void Matrix::setSize(int a){ for (int i=0; i<a; i++) for (int j=0; j<a; j++) element[i][j]=0; size = a;}void Matrix::setModulo(long long a){ modulo = a;}Matrix Matrix::operator* (Matrix param){ Matrix product; product.setSize(size); product.setModulo(modulo); for (int i=0; i<size; i++) for (int j=0; j<size; j++) for (int k=0; k<size; k++) { product.element[i][j]+=element[i][k]*param.element[k][j]; product.element[i][j]%=modulo; } return product;}Matrix Matrix::power(int exp){ Matrix res,A; A=*this; res.setSize(size); res.setModulo(modulo); for(int i=0;i<size;i++) res.element[i][i]=1; while(exp) { if(exp&1) res=res*A; exp>>=1; A=A*A; } return res;}long long a[60];Matrix m;int n,k;int main(){ int cs; m.setModulo(1000000000+7); cin>>cs; while(cs--) { cin>>n>>k; m.setSize(k); if(k!=1){ m.element[0][0]=1; m.element[0][k-1]=1; for(int i=1;i<k;i++) m.element[i][i-1]=1; } else { m.element[0][0]=2; } if(n<k) { printf("0n"); } else if(n==k) { printf("1n"); } else { a[0]=1; for(int i=1;i<k;i++) a[i]=0; int pw=n-k; m=m.power(pw); long long ans=0; for(int i=0;i<k;i++) ans+=m.element[0][i]*a[i]%10000000007; printf("%lldn",ans); } } return 0;}
