题目链接：http://sdnuoj.rainng.com/problem/show/1085

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 3;
const int mod = 1000000007;
struct mat{
   
	ll m[maxn][maxn];
};

mat mul(mat x, mat y, ll len) {
   
	mat tmp;
	for(int i=0; i<len; i++) {
   
		for(int j=0; j<len; j++) {
   
			tmp.m[i][j]=0;
			for(int k=0; k <len; k++) {
   
				tmp.m[i][j]+=(x.m[i][k]*y.m[k][j])%mod;
			}
			tmp.m[i][j]%=mod;
		}
	}
	return tmp;
}

mat matpow(mat x, mat y, ll num) {
   
	while(num>0) {
   
		if(num&1) {
   
			y=mul(y,x,3); 
	}
		x=mul(x,x,3);
		num=num>>1;
	}
	return y;
}

int main()
{
   
	mat res;
	ll n;
	while(~scanf("%lld", &n))
	{
   
		for(int i=0; i<maxn; i++)
			for(int j=0; j<maxn; j++)
				res.m[i][j]=0;
		for(int i=0; i<maxn; i++)
			res.m[0][i]=1;
		res.m[1][0]=1;
		res.m[2][1]=1;
		if(n==1)
            printf("1\n");
        else if(n==2)
            printf("2\n");
        else if(n==3)
            printf("4\n");
		res=matpow(res,res,n-2);
		printf("%lld\n",((4*res.m[2][0])%mod+(2*res.m[2][1])%mod+res.m[2][2]%mod)%mod);
		
	}
	return 0;
}