#include<bits/stdc++.h>
using namespace std;

typedef vector<vector<long long> > mat;

long long MOD = 1000000007;

long long remainder(long long a, long long mod){
    if(a>=0){
        return a%mod;
    }else{
        return (a+(abs(a)/mod+1)*mod)%mod;
    }
}

mat modmulti(mat A, mat B){
    long long r=A.size();
    long long m=A[0].size();
    long long c=B[0].size();
    vector<long long> O(c,0);
    mat C(r,O);
    long long i,j,k;
    for(i=0; i<r; i++){
        for(j=0; j<c; j++){
            for(k=0; k<m; k++){
                C[i][j]+=A[i][k]*B[k][j];
                C[i][j]=remainder(C[i][j],MOD);
            }
        }
    }
    return C;
}

mat modpow(mat A, long long n) {
    vector<long long> O(A.size(),0);
    mat res(A.size(),O);
    for(long long i=0; i<A.size(); i++){
        res[i][i]=1;
    }
    while (n > 0) {
        if (n & 1) res = modmulti(res,A);
        A = modmulti(A,A);
        n >>= 1;
    }
    return res;
}

int main(){
    //input
    long long N,M;
    cin >> N >> M;
    MOD=M;

    //calc
    vector<long long> O(2,0);
    mat A(2,O);
    A[0][0]=0;
    A[0][1]=1;
    A[1][0]=1;
    A[1][1]=1;
    mat ApowN=modpow(A,N-1);
    vector<long long> verO(1,0);
    mat v(2,verO);
    v[1][0]=1;
    mat ans=modmulti(ApowN,v);

    //output
    cout << ans[0][0] << endl;
    return 0;
}