#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;
}

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8ZnVuY3Rpb25hbD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCmNvbnN0ZXhwciBpbnQga01heE0gPSAxMDAwMDAwICsgMTsKCmludCBmaWJfMVs2ICoga01heE1dOwppbnQgZmliXzJbMzYgKiBrTWF4TV07CgppbnQgbWFpbigpIHsKICAgIGNpbi50aWUoMCk7CiAgICBpb3NfYmFzZTo6c3luY193aXRoX3N0ZGlvKGZhbHNlKTsKCiAgICBmdW5jdGlvbjxpbnQoaW50IFtdLCBjb25zdCBpbnQmKT4gZ2V0X3BlcmlvZCA9IFtdIChpbnQgZmliW10sIGNvbnN0IGludCYgeCkgewogICAgICAgIGZpYlswXSA9IDE7CiAgICAgICAgZmliWzFdID0gMTsKICAgICAgICBpbnQgaSA9IDI7CiAgICAgICAgZG8gewogICAgICAgICAgICBmaWJbaV0gPSAoZmliW2kgLSAxXSArIGZpYltpIC0gMl0pOwogICAgICAgICAgICBpZiAoZmliW2ldID49IHgpIHsKICAgICAgICAgICAgICAgIGZpYltpXSAtPSB4OwogICAgICAgICAgICB9CiAgICAgICAgICAgIGkgKz0gMTsKICAgICAgICB9IHdoaWxlIChmaWJbaSAtIDFdICE9IDEgb3IgZmliW2kgLSAyXSAhPSAxKTsKICAgICAgICByZXR1cm4gaSAtIDI7CiAgICB9OwoKICAgIGludCBuLCBtOwogICAgd2hpbGUgKGNpbiA+PiBuID4+IG0pIHsKICAgICAgICBpbnQgcGVyaW9kID0gZ2V0X3BlcmlvZChmaWJfMSwgbSk7CiAgICAgICAgaW50IHBlcmlvZF9vZl9wZXJpb2QgPSBnZXRfcGVyaW9kKGZpYl8yLCBwZXJpb2QpOwogICAgICAgIGNvdXQgPDwgZmliXzFbKGZpYl8yWyhuIC0gMSkgJSBwZXJpb2Rfb2ZfcGVyaW9kXSAtIDEgKyBwZXJpb2QpICUgcGVyaW9kXSA8PCAnXG4nOwogICAgfQogICAgcmV0dXJuIDA7Cn0=

MSAxMDAKMiAxMDAKMyAxMDAKNCAxMDAKNSAxMDAKNSAyCjYgMTAw

1 100
2 100
3 100
4 100
5 100
5 2
6 100