long long binpow(long long a, long long b) {
long long res = 1;
while (b > 0) {
if (b & 1) res = res * a;
a = a * a;
b >>= 1;
}
return res;
}long long binpow(long long a, long long b) {
long long res = 1;
while (b > 0) {
if (b & 1) res = res * a % MOD;
a = a * a % MOD;
b >>= 1;
}
return res % MOD;
}#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=3,mod=1e9+7;
struct Matrix{
int mat[N][N];
Matrix(){memset(mat,0,sizeof(mat));}
Matrix operator*(const Matrix& o)const{
Matrix res;
for(int i=0;i<N;++i){
for(int k=0;k<N;++k){
for(int j=0;j<N;++j){
res.mat[i][j]=(res.mat[i][j]+mat[i][k]*o.mat[k][j])%mod;
}
}
}
return res;
}
};
Matrix qpow(Matrix a,int b){
Matrix res;
for(int i=0;i<N;++i)res.mat[i][i]=1;
while(b){
if(b&1)res=res*a;
a=a*a;
b>>=1;
}
return res;
}