#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=