/*少说话,多做事*/ #include <cstdio> #include <cstring> #include <string> #include <cmath> #include <iostream> #include <algorithm> #include <vector> #include <stack> #include <sstream> #include <map> #include <set> #include <queue> #include <stdlib.h> //#include<bits/stdc++.h> //ios::sync_with_stdio(0); //cin.tie(0); //cout.tie(0); typedef long long ll; using namespace std; /* */ const int maxn = 3; const ll mod=1e9+7; struct node { ll m[maxn][maxn]; }unit; void init() //初始化 ,将unit设为单位数组 { for(int i=0;i<maxn;i++) { for (int j=0;j<maxn;j++) { if(i==j) unit.m[i][j]=1; else unit.m[i][j]=0; } } } node matmul(node a,node b) //定义矩阵的乘法 -> 矩阵乘以矩阵,返回的是矩阵 { node ans; ll tmp =0; for(int i=0;i<maxn;i++) { for(int j=0;j<maxn;j++) { tmp=0; for(int k=0;k<maxn;k++) { tmp=(tmp + a.m[i][k] * b.m[k][j])%mod; } ans.m[i][j]=tmp; } } return ans; } node qaq (node x , ll n) //计算数组^b, --》比如设A为数组,B为一个数,则qaq求的是A^B { init(); //将unit初始化为单位矩阵 ,一开始都是从单位矩阵开始乘的。 -》 就一直按照unit变化,最后得出的答案就是从unit中找,这道题是m[1][0]为fn while(n!=0) { if(n%2==1) //如果b是奇数 { unit = matmul(unit, x); //ans是矩阵,unit也是矩阵 } x = matmul(x, x); n>>=1; } return unit; } int main() { ll n; while(cin >> n) { if(n==1) cout << "1" << endl; else if(n==2) cout << "2" << endl; else if(n==3) cout << "4" << endl; else { node x = {1,1,1,1,0,0,0,1,0}; x = qaq(x, n-3); cout << (x.m[0][0]*4%mod + x.m[0][1]*2%mod + x.m[0][2]*1%mod)%mod << endl; } } return 0; }