http://acm.hdu.edu.cn/showproblem.php?pid=4291

凡是取模的都有循环节-----常数有，矩阵也有，并且矩阵的更奇妙：

g(g(g(n))) mod 10⁹ + 7  最外层MOD=1e9+7  能够算出g(g(n))的循环节222222224。进而算出g(n)的循环节183120LL。然后由内而外计算就可以

凝视掉的是求循环节的代码

//#pragma comment(linker, "/STACK:102400000,102400000")

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <string>

#include <iostream>

#include <iomanip>

#include <cmath>

#include <map>

#include <set>

#include <queue>

using namespace std;

#define ls(rt) rt*2

#define rs(rt) rt*2+1

#define ll long long

#define ull unsigned long long

#define rep(i,s,e) for(int i=s;i<e;i++)

#define repe(i,s,e) for(int i=s;i<=e;i++)

#define CL(a,b) memset(a,b,sizeof(a))

#define IN(s) freopen(s,"r",stdin)

#define OUT(s) freopen(s,"w",stdout)

const ll ll_INF = ((ull)(-1))>>1;

const double EPS = 1e-8;

const double pi = acos(-1.0);

const int INF = 100000000;

const ll MOD[3] = {183120LL,222222224LL,1000000007LL};

const int N = 2;

struct Matrix{

    ll m[N][N];

    //int sz;//矩阵的大小

};

Matrix I= {3LL,1LL,//要幂乘的矩阵

           1LL,0LL,

          };

Matrix unin={1LL,0LL,//单位矩阵

             0LL,1LL,

            };

Matrix matrixmul(Matrix a,Matrix b,long long  mod)//矩阵a乘矩阵b

{

    Matrix c;

    for(int i=0; i<N; i++)

        for(int j=0; j<N; j++)

        {

            c.m[i][j]=0LL;

            for(int k=0; k<N; k++)

                c.m[i][j]+=(a.m[i][k]*b.m[k][j])%mod;

            c.m[i][j]%=mod;

        }

    return c;

}

Matrix quickpow(long long n,long long  mod)

{

    Matrix m=I,b=unin;//求矩阵I的n阶矩阵

    while(n>=1)

    {

        if(n&1)

            b=matrixmul(b,m,mod);

        n=n>>1;

        m=matrixmul(m,m,mod);

    }

    return b;

}

ll solve(ll n)

{

    ll ans;

    Matrix ret;

    ret.m[0][0]=n;

    for(int i=0;i<3;i++)

    {

        if(ret.m[0][0]!=0 && ret.m[0][0]!=1)ret=quickpow(ret.m[0][0]-1,MOD[i]);

    }

    return ret.m[0][0];

}

int main()

{

    //precal();

    ll n;

    while(~scanf("%I64d",&n))

    {

        if(n==0){puts("0");continue;}

        if(n==1){puts("1");continue;}

        //printf("%I64d\n",solve(n));

        cout << solve(n)%1000000007LL << endl;

    }

    return 0;

}

hdu 4291 矩阵幂  循环节