#include <iostream>

using namespace std;

int binpow(long long n, int m){
    int tmp[2][2]= {{0, 0}, {0, 0}};
    int result [2][2] = {{1, 0}, {0, 1}};
    int a [2][2] = {{0, 1}, {1, 1}};

    while(n != 0){
        if(n % 2 == 1){
            //не смог вынести умножение отдельно в функцию так как забыл как передавать в нее двумерный массив
            //по-моему int** но точно не помню
            for(int i = 0; i < 2; i++){
                for(int j = 0; j < 2; j++){
                    tmp[i][j] = 0;
                    for(int k = 0; k < 2; k++){
                        tmp[i][j] += result[i][k]*a[k][j] % m;

                    }
                }
            }
            //конец умножения
            //присваивание значениям матрицы result значений матрицы tmp

            for(int i = 0; i < 2; i++){
                for(int j = 0; j < 2; j++){
                    result[i][j] = tmp[i][j];
                }
            }
            //бинарное возведение в степень
            //n =  n - 1;
        }
        //бинарное возведение в степень(условие чётности)
        for(int i = 0; i < 2; i++){
                for(int j = 0; j < 2; j++){
                    tmp[i][j] = 0;
                    for(int k = 0; k < 2; k++){
                        tmp[i][j] += a[i][k]*a[k][j] % m;

                    }
                }
            }
            //
            for(int i = 0; i < 2; i++){
                for(int j = 0; j < 2; j++){
                    a[i][j] = tmp[i][j];
                }
            }

        n = n / 2;
        //вывод сделан чтобы посмотреть значения матрицы Result
        for(int i = 0; i < 2; i++){
            for(int j = 0; j < 2; j++){
                cout << result[i][j] << " ";
            }
            cout << endl;
        }
        for(int i = 0; i < 2; i++){
            for(int j = 0; j < 2; j++){
                cout << a[i][j] << " ";
            }
            cout << endl;
        }


    }
    //по результату вроде работает но выдает по номеру на 1 число дальше или я обсчитался
        return result[1][1];



}

int main()
{
    long long n = 0;
    int m = 0;
    cin >> n >> m;

    cout << binpow(n, m) << endl;
    return 0;
}