#include<bits/stdc++.h>
using namespace std;
#define int long long
const int n=3,N=n+5;
int num,mod;
struct matrix{
    int a[N][N];
    matrix(){
        memset(a,0,sizeof(a));
    }
};
matrix operator*(matrix a,matrix b){
    matrix ret;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            for(int k=1;k<=n;k++){
                ret.a[i][j]=(ret.a[i][j]+a.a[i][k]*b.a[k][j])%mod;
            }
        }
    }
    return ret;
}
signed main(){
    cin>>num>>mod;
    matrix ret;
    ret.a[1][1]=1,ret.a[1][2]=1,ret.a[1][3]=0;
    matrix base;
    base.a[1][1]=1,base.a[1][2]=1,base.a[1][3]=1,base.a[2][2]=1,base.a[2][3]=1,base.a[3][2]=1;
    while(num){
        if(num%2){
            ret=ret*base;
        }
        base=base*base,num/=2;
    }
    cout<<ret.a[1][1];
}

都输出1 思路是S[i]=斐波那契前i项 之后直接矩阵快速幂