#include #include using std::vector; const int mod = 1e9+7; int f[100005][2]; int c[10][10]; int a[10][10]; int power(int a,int b){ int res = 1; while(b){ if(b%2) res = res*1ll*a%mod; a = a*1ll*a%mod; b /= 2; } return res; } void mul(int a[10][10],int b[10][10],int n){ for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++){ c[i][j] = 0; for(int k = 1; k <= n; k++){ int add = a[i][k]*1ll*b[k][j]%mod; c[i][j] += add; if(c[i][j] >= mod) c[i][j] -= mod; } } } for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++) a[i][j] = c[i][j]; } } void power(int a[10][10],int b,int n){ int res[10][10]; for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++){ if(i==j) res[i][j] = 1; else res[i][j] = 0; } } while(b){ if(b%2) mul(res,a,n); mul(a,a,n); b /= 2; } for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++) a[i][j] = res[i][j]; } } int main(){ int T; scanf("%d",&T); while(T--){ int n = 3; int m,d; scanf("%d%d",&m,&d); int invn = power(n,mod-2); // f[i][j]: can guess i time, now at j f[0][1] = 1; f[0][0] = 0; for(int i = 1; i <= 1; i++){ for(int j = 0; j < 2; j++){ f[i][j] = 0; if(j){ // stay f[i][j] = (f[i][j] + f[i-1][j]*1ll*invn)%mod; // run if(i>=2) f[i][j] = (f[i][j] + f[i-2][0]*1ll*invn%mod*1ll*(n-1)%mod)%mod; } else{ // stay f[i][j] = (f[i][j] + f[i-1][j]*1ll*invn)%mod; if(i>=2){ f[i][j] = (f[i][j] + f[i-2][0]*1ll*invn%mod*1ll*(n-2)%mod)%mod; f[i][j] = (f[i][j] + f[i-2][1]*1ll*invn%mod*1ll*(1)%mod)%mod; } } } } printf("%d\n",f[m][1]); vector aa = { 0,0,1,0, 0,0,0,1, (n-2)*1ll*invn%mod,invn,invn,0, (n-1)*1ll*invn%mod,0,0,invn, }; int tot = 0; for(int i = 1; i <= 4; i++){ for(int j = 1; j <= 4; j++) a[i][j] = aa[tot++]; } power(a,m-1,4); int ans = 0; vector dp = {-1,f[0][0],f[0][1],f[1][0],f[1][1]}; for(int i = 1; i <= 4; i++){ int add = dp[i]*1ll*a[4][i]%mod; ans = (ans + add)%mod; } int fail = 1-ans; if(fail < 0) fail += mod; fail = power(fail,d); ans = 1-fail; if(ans < 0) ans += mod; printf("%d\n",ans); } return 0; }