观察到dp柿子可以压成一维，矩阵快速幂处理

#include<bits/stdc++.h>
#define int long long
#define maxn 200005
using namespace std;
const int mod=1e9+7;
int T,n,k;
struct sign{
	int hang,lie,block[10][10];
};
sign operator*(const sign &a,const sign &b){
	sign c;
	c.hang=a.lie;c.lie=b.hang;
	for(int i=1;i<=c.hang;++i)
	for(int j=1;j<=c.lie;++j)
	c.block[i][j]=0;
	for(int i=1;i<=c.hang;++i){
		for(int j=1;j<=c.lie;++j){
			for(int k=1;k<=a.lie;++k){
				c.block[i][j]=(c.block[i][j]+a.block[i][k]*b.block[k][j])%mod;
			}
		}
	}
	return c;
}
sign sign_pow(sign a,int k){
	sign res;
	res.hang=res.lie=a.hang;
	for(int i=1;i<=a.hang;++i)
		for(int j=1;j<=a.lie;++j)
			res.block[i][j]=0;
	for(int i=1;i<=a.hang;++i)
		res.block[i][i]=1;
	while(k){
		if(k&1)res=res*a;
		a=a*a;
		k/=2;
	}
	return res;
}
sign e,czr,ans;
void solve(){
	cin>>n>>k;k%=mod;
	e.hang=3;e.lie=3;e.block[1][1]=k+1;e.block[1][3]=e.block[2][1]=e.block[3][3]=1;
	czr.hang=3;czr.lie=1;czr.block[1][1]=((1+k)*(1+k)+k+1)%mod;czr.block[2][1]=(1+k)%mod;czr.block[3][1]=(1+k)%mod;
	if(n==1){
		cout<<(1+k)%mod<<"\n";
		return;
	}
	if(n==2){
		cout<<((1+k)*(1+k)+k+1)%mod<<"\n";
		return;
	}
	ans=sign_pow(e,n-2)*czr;
	cout<<ans.block[1][1]<<"\n";return;
}
signed main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>T;while(T--)solve();
	return 0;
}