hdu 4291 A Shott problemは法則と行列を探して素早くべきです。

http://www.cnblogs.com/kuangbin/archive/2012/09/17/2688852.html

//author: CHC
//First Edit Time:	2014-10-18 16:11
//Last Edit Time:	2014-10-18 23:27
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <algorithm>
#include <limits>
using namespace std;
typedef long long LL;
const int MAXN=1e+4;
const int MAXM=1e+5;
const int INF= numeric_limits<int>::max();
const LL LL_INF= numeric_limits<LL>::max();
#define N 2
LL MOD=1e+9 +7;
// a = a * b
void matric_mul(LL a[][N],LL b[][N])
{
	int i,j,k;
    LL tmp[N][N];
    memset(tmp,0,sizeof(tmp));
	for(i=0;i<N;i++)
	{
		for(j=0;j<N;j++)
		{
			for(k=0;k<N;k++)
			{
				tmp[i][j] = (tmp[i][j]+a[i][k]*b[k][j]) % MOD;
                if(tmp[i][j]<0)tmp[i][j]+=MOD;
			}
		}
	}
	for(i=0;i<N;i++)
	{
		for(j=0;j<N;j++)
		{
			a[i][j] = tmp[i][j];
		}
	}
}
LL quickpow(LL n){
    if(n==0)return 0LL;
    //int ans=1,tmp=base;
    LL ans[2][2]={{1,0},{0,1}};
    LL tmp[2][2]={{0,1},{1,3}};
    while(n){
        if(n&1)matric_mul(ans,tmp);
            //ans=(ans*tmp)%MOD;
        //tmp=(tmp*tmp)%MOD;
        matric_mul(tmp,tmp);
        n>>=1;
    }
    return ans[0][1];
}
int main()
{
    LL n;
    while(~scanf("%I64d",&n)){
        MOD=183120;
        LL n1=quickpow(n);
        MOD=222222224;
        LL n2=quickpow(n1);
        MOD=1000000007;
        LL n3=quickpow(n2);
        printf("%I64d
",n3);
    }
    return 0;
}