#include<bits/stdc++.h>
using namespace std;
#define int long long
const int lim = 2;
struct matrix {
	long long m[10005][10005];
};
matrix f, res;
int n, p;
long long m;
void init(matrix &x) {
	for (int i = 1; i <= lim; i++) {
		for (int j = 1; j <= lim; j++) {
			if (i == j) x.m[i][j] = 1ll;
			else x.m[i][j] = 0ll;
		}
	}
}
void multiple(matrix &x, matrix &y, matrix &z) {
	memset(z.m, 0, sizeof(z.m));
	for (int i = 1; i <= lim; i++) {
		for (int j = 1; j <= lim; j++) {
			if (x.m[i][j]) {
				for (int k = 1; k <= lim; k++) {
					z.m[i][k] += x.m[i][j] * y.m[j][k];
					z.m[i][k] %= m;
				}
			}
		}
	}
}
void ksm (int k) {
	init(res);
	matrix tmp = f, t;
	while (k) {
		if (k & 1) {
			multiple(res, tmp, t);
			res = t;
		}
		multiple(tmp, tmp, t);
		tmp = t;
		k >>= 1;
	}
}
long long solve() {
	if (n <= 2) return 1ll;
	ksm(n - 2);
	long long ret = res.m[1][1] + res.m[2][1];
	if (ret >= m) ret -= m;
	return ret;
}
signed main() {
	cin >> n >> p;
	m = p;
	f.m[1][1] = 1;
	f.m[1][2] = 1;
	f.m[2][1] = 1;
	f.m[2][2] = 0;
	long long res = solve();
	cout << res << endl;
	return 0;
}