学步园

完全被虐啊，见识太少，完全没有意识到取模必定会有循环节的问题，所以束手无策。。。。。

先暴力本地算出最外层取模的循环节，在依次往里推循环节，还需要注意两个long long型相乘的溢出问题，不过这道题好像没有这么极端的数据

code：

#include <cstdio>
#include <cstring>
#define LL __int64
using namespace std;
LL modular_multi(LL a, LL b, LL c) {
    LL res;
    res = 0;
    while (b) {
        if (b & 1) {
            res += a;
            if (res >= c) {
                res -= c;
            }
        }
        a <<= 1;
        if (a >= c) {
            a -= c;
        }
        b >>= 1;
    }
    return res;
}
struct Matrix
{
    LL Mat[2][2];
    void init()
    {
        memset(Mat,0,sizeof(Mat));
    }
    void unit()
    {
        init();
        Mat[0][0]=Mat[1][1]=1;
    }
    Matrix()
    {
        init();
    }
    Matrix Mul(Matrix b,LL mod)
    {
        Matrix res;
        res.init();
        for(int i=0;i<2;i++)
        {
            for(int j=0;j<2;j++)
            {
                for(int k=0;k<2;k++)
                {
                    res.Mat[i][j]=(res.Mat[i][j] + modular_multi(Mat[i][k],b.Mat[k][j],mod)) %mod;
                }
            }
        }
        return res;
    }
    Matrix Pow(LL exp,LL mod)
    {
        Matrix tmp=*this,res;
        res.unit();
        while(exp)
        {
            if( exp&1)
            {
                res=res.Mul(tmp,mod);
            }
            exp >>= 1;
            tmp=tmp.Mul(tmp,mod);
        }
        return res;
    }
    void Print()
    {
        puts("------------------");
        for(int i=0;i<2;i++)
        {
            for(int j=0;j<2;j++)
            {
                printf(" %I64d",Mat[i][j]);
            }
            puts("");
        }
    }
}a;
LL solve(LL n,LL mod)
{
    if(n==0)
    {
        return 0;
    }
    return a.Pow(n-1,mod).Mat[0][0];
}
int main()
{
    LL n,ans;
    a.Mat[0][0]=3;
    a.Mat[0][1]=1;
    a.Mat[1][0]=1;
    a.Mat[1][1]=0;
    while(~scanf("%I64d",&n))
    {
        ans=solve(solve(solve(n,183120),222222224),1000000007);
        printf("%I64d\n",ans);
    }
    return 0;
}