#include <iostream>
#include <functional>
using namespace std;

constexpr int kMaxM = 1000000 + 1;

int fib_1[6 * kMaxM];
int fib_2[36 * kMaxM];

int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(false);

    function<int(int [], const int&)> get_period = [] (int fib[], const int& x) {
        fib[0] = 1;
        fib[1] = 1;
        int i = 2;
        do {
            fib[i] = (fib[i - 1] + fib[i - 2]);
            if (fib[i] >= x) {
                fib[i] -= x;
            }
            i += 1;
        } while (fib[i - 1] != 1 or fib[i - 2] != 1);
        return i - 2;
    };

    int n, m;
    while (cin >> n >> m) {
        int period = get_period(fib_1, m);
        int period_of_period = get_period(fib_2, period);
        cout << fib_1[(fib_2[(n - 1) % period_of_period] - 1 + period) % period] << '\n';
    }
    return 0;
}