#include #define assn(n,a,b) assert(n<=b && n>=a) using namespace std; #define pb push_back #define mp make_pair #define clr(x) x.clear() #define sz(x) ((int)(x).size()) #define F first #define S second #define REP(i,a,b) for(i=a;i PII; typedef vector VPII; typedef vector VI; typedef vector VVI; typedef long long LL; #define MOD 1000000007 typedef vector < vector < LL > > matrix; //define matrix matrix I; //identity matrix // multiply two matrices matrix multiply(matrix A, matrix B) { int K=(int)A.size(); matrix C(K, vector(K)); rep(i, K) rep(j, K) rep(k, K) { C[i][j] = C[i][j] + (A[i][k] * B[k][j]) % MOD; if(C[i][j]>=MOD) C[i][j]-=MOD; } return C; } //find N'th power of matrix T matrix mpow(matrix T, LL N) { if(N==0)return I; if(N==1)return T; matrix ret=mpow(T,N/2); matrix ret1=multiply(ret,ret); if(N%2==0)return ret1; else return multiply(ret1,T); } int main() { int t; cin >> t; while(t--) { LL N,n; cin >> N >> n; //matrix for even row matrix even(n,vector < LL >(n)); //matrix for odd row matrix odd(n,vector < LL >(n)); I.resize(n); //build the matrices for(int i=0; i=0) even[i][i-1]=odd[i][i-1]=1; if(i+1=MOD)ret-=MOD; } cout << ret << endl; } return 0; }