Plant(𝐶𝑜𝑑𝑒𝐹𝑜𝑟𝑐𝑒𝑠 − 185𝐴)

#include<iostream>

#include<cstring>

using namespace std;

const int maxn=,mod=;

struct Matrix

{

    long long  mat[maxn][maxn];

    Matrix operator*(const Matrix& m)const///重载*运算符，使其能进行矩阵相乘的运算

    {

        Matrix tmp;

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

        {

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

            {

                tmp.mat[i][j] = ;

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

                {

                    tmp.mat[i][j] += mat[i][k]*m.mat[k][j]%mod;

                    tmp.mat[i][j] %= mod;

                }

            }

        }

        return tmp;

    }

};

Matrix m;

void init()

{

    m.mat[][]=;

    m.mat[][]=;

    m.mat[][]=;

    m.mat[][]=;

}

long long run(long long n)

{

    Matrix ans;

    memset(ans.mat,,sizeof(ans.mat));

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

        ans.mat[i][i]=;

    while(n)

    {

        if(n&)

            ans=ans*m;

        n>>=;

        m=m*m;

    }

    return ans.mat[][];

}

int main()

{

    long long n;

    while(cin>>n)

    {

        init();

        cout<<run(n)<<endl;

    }

    return ;

}