思路：

如图找到推导公式，然后一通乱搞就好了

要开long long，否则红橙作伴

代码：

#include<set>

#include<cstring>

#include<cstdio>

#include<algorithm>

#define ll long long

const int maxn = 3;

const int MOD = 1000000000+7;

const int INF = 0x3f3f3f3f;

using namespace std;

ll m;

struct Mat{

    ll s[maxn][maxn];

    void init(){

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

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

                s[i][j] = 0;

    }

};

Mat mul(Mat a,Mat b){

    Mat t;

    t.init();

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

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

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

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

            }

        }

    }

    return t;

}

Mat pow_mat(Mat p,int n){

    Mat ret;

    ret.init();

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

        ret.s[i][i] = 1;

    while(n){

        if(n & 1) ret = mul(ret,p);

        p = mul(p,p);

        n >>= 1;

    }

    return ret;

}

int main(){

    ll n;

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

        Mat A,B,T;

        memset(T.s,0,sizeof(T.s));

        memset(B.s,0,sizeof(B.s));

        T.s[0][0] = T.s[1][0] = T.s[0][2] = T.s[2][2] = 1;

        T.s[0][1] = 2;

        if(n == 1) printf("%lld\n",1%m);

        else if(n == 2) printf("%lld\n",2%m);

        else{

            B.s[0][0] = 2,B.s[1][0] = 1,B.s[2][0] = 1;

            A = pow_mat(T,n - 2);

            A = mul(A,B);

            printf("%lld\n",A.s[0][0]);

        }

    }

    return 0;

}