Problem Description

　　According to a research, VIM users tend to have shorter fingers, compared with Emacs users.
　　Hence they prefer problems short, too. Here is a short one:
　　Given n (1 <= n <= 10¹⁸), You should solve for 
g(g(g(n))) mod 10⁹ + 7
　　where
g(n) = 3g(n - 1) + g(n - 2)
g(1) = 1
g(0) = 0

 

Input

　　There are several test cases. For each test case there is an integer n in a single line.
　　Please process until EOF (End Of File).

 

Output

　　For each test case, please print a single line with a integer, the corresponding answer to this case.

 

Sample Input

 

Sample Output

 

Source

 

/*

 * Author: lyucheng

 * Created Time:  2017年05月20日 星期六 16时40分42秒

 * File Name: HDU-4291-A_Short_problem.cpp

 */

 /*

 * 题意:让你求g(g(g(n)))mod 1e9+7,其中g(n)=3*g(n-1)+g(n-2)

 *

 *

 * 思路:g(n)可以通过矩阵快速幂求出来,但是干后分别求出各自的循环节,能得到第一个循环节是222222224,

 *      第二个循环节是183120

 * */

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <string>

#include <vector>

#include <stack>

#include <queue>

#include <set>

#include <time.h>

#define LL long long

#define maxn 3

using namespace std;

LL n;

LL mod;

/********************************矩阵快速幂**********************************/

class Matrix {

    public:

        LL a[maxn][maxn];

        void init() {

            memset(a,,sizeof(a));

        }

        Matrix operator +(Matrix b) {

            Matrix c;

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

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

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

            return c;

        }

        Matrix operator +(LL x) {

            Matrix c = *this;

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

                c.a[i][i] += x;

            return c;

        }

        Matrix operator *(Matrix b)

        {

            Matrix p;

            p.init();

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

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

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

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

            return p;

        }

        Matrix power(LL t) {

            Matrix ans,p = *this;

            ans.init();

            ans.a[][]=;

            ans.a[][]=;

            while (t) {

                if (t & )

                    ans=ans*p;

                p = p*p;

                t >>= ;

            }

            return ans;

        }

}unit,init;

/********************************矩阵快速幂**********************************/

int main(int argc, char* argv[])

{

    // freopen("in.txt","r",stdin);

    //freopen("out.txt","w",stdout;

    while(scanf("%lld",&n)!=EOF){

        if(n<){

            printf("%lld\n",n);

            continue;

        }

        //首先求最里面的g(n)

        mod=;

        unit.init();

        unit.a[][]=,unit.a[][]=,unit.a[][]=,unit.a[][]=;

        init.a[][]=,init.a[][]=,init.a[][]=,init.a[][]=;

        init=init.power(n-);

        unit=unit*init;

        n=unit.a[][];

        if(n>=){//很重要,要不然当n<2的时候矩阵乘法就会死循环

            mod=;

            unit.init();

            unit.a[][]=,unit.a[][]=,unit.a[][]=,unit.a[][]=;

            init.a[][]=,init.a[][]=,init.a[][]=,init.a[][]=;

            init=init.power(n-);

            unit=unit*init;

            n=unit.a[][];

        }

        if(n>=){//很重要,要不然当n<2的时候矩阵乘法就会死循环

            mod=;

            unit.init();

            unit.a[][]=,unit.a[][]=,unit.a[][]=,unit.a[][]=;

            init.a[][]=,init.a[][]=,init.a[][]=,init.a[][]=;

            init=init.power(n-);

            unit=unit*init;

            n=unit.a[][];

        }

        printf("%lld\n",n);

    }

    return ;

}