Fib_Log(N)

#include <iostream>
#include <vector>
using namespace std;
typedef unsigned long long ull;
vector<vector<ull>> matrix_multiply(vector<vector<ull>>& A, vector<vector<ull>> B, ull& mod) {
    vector<vector<ull>> C = { {0, 0}, {0, 0} };
    C[0][0] = (A[0][0] * B[0][0] + A[0][1] * B[1][0]) % mod;
    C[0][1] = (A[0][0] * B[0][1] + A[0][1] * B[1][1]) % mod;
    C[1][0] = (A[1][0] * B[0][0] + A[1][1] * B[1][0]) % mod;
    C[1][1] = (A[1][0] * B[0][1] + A[1][1] * B[1][1]) % mod;
    return C;
}
vector<ull> decomp(ull n, vector<ull>& divs) {
    while (n != 0) {
        if (n % 2 == 0) {
            divs.push_back(0);
            n /= 2;
        }
        else {
            divs.push_back(1);
            n--;
        }

    }
    return divs;
}
vector<vector<ull>> pow(vector<vector<ull>> x, ull n, vector<vector<ull>> I, ull& mod) {
    if (n == 0) return I;
    else if (n == 1) return x;
    else {
        vector<ull> divs;
        divs = decomp(n, divs);
        for (ull i = divs.size() - 1; i > 0; i--) {
            if (divs [i-1] == 0) x = matrix_multiply(x, x, mod);
            else  x = matrix_multiply(x, I, mod);
        }
    }
    return x;
}

ull fib(ull n, ull& mod) {
    vector<vector<ull>>F = { {1, 1}, {1, 0} };
    F = pow(F, n, F, mod);
    return F[0][1];
}

int main()
{
    ull n, mod;
    cin >> n >> mod;
    cout << fib(n, mod);
    return 0;
}