1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57
| #include<bits/stdc++.h> using namespace std;
using ll=long long; using vll=vector<ll>; using Mer=vector<vll>;
const ll MOD=1e9+7;
Mer operator*(Mer a,Mer b){ Mer ret(a.size(),vll(b[0].size())); for(int i=0;i<a.size();++i){ for(int j=0;j<b[0].size();++j){ for(int k=0;k<a.size();++k){ ret[i][j]=(ret[i][j]+a[i][k]*b[k][j])%MOD; } } } return ret; }
Mer POW(Mer a,ll x){ Mer ret(a.size(),vll(a[0].size(),0)); for(int i=0;i<a.size();++i) ret[i][i]=1; while(x>0){ if(x&1) ret=ret*a; a=a*a; x>>=1; } return ret; }
int main(){ ios::sync_with_stdio(0);cin.tie(0);
ll n; cin>>n;
if(n<=3){ cout<<1<<"\n"; }else{ Mer t=Mer({ {0,1,2,1}, {1,0,0,0}, {0,1,0,0}, {0,0,1,0} });
t=POW(t,n-3);
Mer ans=Mer({{1},{1},{1},{0}});
ans=t*ans;
cout<<ans[0][0]<<"\n"; } }
|