#include <iostream>

long long get_fibonaccihuge(long long n, long long m)
{
    long long a, b, c, i; //, r, g, R;
    long long g;

    // length of pisano period pi(m)
    a = 0; b = 1;
    g = 0;
    /* Fi mod m */
    for (i = 0; ; i++) {
        c = a + b;
        if (c >= m)
            c -= m;
        // start pattern is 011
        if (c == 0)
            g = ((g == 0) ? 1 : 0);
        else if (g == 1)
            g = ((c == 1) ? 2 : 0);
        else if (g == 2) {
            if (c == 1)
                break;
            g = 0;
        }
        /* if (g == 2) { */
        /*     i += 1; */
        /*     break; */
        /* } */

        a = b;
        b = c;
    }

    /* g = n % i; */
    g = (n / i);
    g = n - (g * i);

    if (g <= 1)
        return g;

    /* Fg mod m */
    a = 0; b = 1;
    for (i = 1; i < g; i++) {
        c = a + b;
        if (c >= m)
            c -= m;
        a = b;
        b = c;
    }

    return b;
}

int main() {
    long long n, m;
    std::cin >> n >> m;
    std::cout << get_fibonaccihuge(n, m) << '\n';
}