Untitled

#include <iostream>
#include <cmath>
#include <cstdio>
#include <string>
#include <cstring>
#include <algorithm>
using std::string; 
using namespace std;

// 矩阵乘法，并对结果进行模运算
void multiply(long long a[2][2], long long b[2][2], long long mod) {
    long long res[2][2];
    res[0][0] = (a[0][0] * b[0][0] + a[0][1] * b[1][0]) % mod;
    res[0][1] = (a[0][0] * b[0][1] + a[0][1] * b[1][1]) % mod;
    res[1][0] = (a[1][0] * b[0][0] + a[1][1] * b[1][0]) % mod;
    res[1][1] = (a[1][0] * b[0][1] + a[1][1] * b[1][1]) % mod;
    // 将结果复制回 a
    a[0][0] = res[0][0];
    a[0][1] = res[0][1];
    a[1][0] = res[1][0];
    a[1][1] = res[1][1];
}

// 矩阵快速幂，并对结果进行模运算
void power(long long base[2][2], long long exp, long long mod) {
    long long res[2][2] = {{1, 0}, {0, 1}}; // 单位矩阵
    while (exp > 0) {
        if (exp % 2 == 1) {
            multiply(res, base, mod);
        }
        multiply(base, base, mod);
        exp /= 2;
    }
    // 将结果复制回 base
    base[0][0] = res[0][0];
    base[0][1] = res[0][1];
    base[1][0] = res[1][0];
    base[1][1] = res[1][1];
}

// 计算费氏数列的第 n 项，并对结果进行模运算
long long fibonacci(long long n, long long mod) {
    if (n == 0) return 0;
    long long T[2][2] = {{1, 1}, {1, 0}};
    power(T, n - 1, mod);
    return T[0][0];
}

int main() {
    long long n;
    long long r;
    cin >> n >> r;
    cout << fibonacci(n, r) << endl;
    return 0;
}