//#define DBG
//
//  main.cpp
//  FMINoStress
//
//  Created by Laur Ion on 11/15/13.
//  Copyright (c) 2013 Laur Ion. All rights reserved.

#include <fstream>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;

long long n;
int t, MOD;

ifstream fin("melodii.in");
ofstream fout("melodii.out");

void inmultire(long long a[][3], long long b[][3]){
    long long c[3][3] = {0};
    int i, j, k;
    for(i = 0; i < 2; ++i)
        for(j = 0; j < 2; ++j)
            for(k = 0; k < 2; ++k)
                c[i][j] = (c[i][j] + ((long long)a[i][k] * b[k][j]%MOD)) % MOD;
    memcpy(a, c, sizeof(c));
}
void solve(){
    long long a[3][3];
    a[0][0] = 0; a[0][1] = 1; a[1][0] = 1; a[1][1] = 1;
    long long sol[3][3];
    sol[0][0] = sol[1][1] = 1;
    //n --;
    for(; n; (n >>=1) ){
        if(n & 1)
            inmultire(sol, a);
        inmultire(a, a);
    }
    fout<<sol[1][1]<<'\n';
}

int main(){
    
    
//    fin>>t>>MOD;
//    while(t){
//        --t;
//        fin>>n;
        solve();
        
//    }
    return 0;
}