矩阵快速幂求调，回皆关

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n, p;

inline int qm(int x) { //光速取模
	if (x < 0) x += p;
	return (x > p ? x - p : x);
}

inline int mul(int a, int b) { //光速乘
	return qm(a * b - (long long)((long double)a * b / p) * p);
}

//inline int mul(int a, int b) { //龟速乘
//	int res = 0;
//	while (b) {
//		if (b & 1) res = qm(res + a);
//		a = qm(a + a);
//		b >>= 1;
//	}
//	return res;
//}

struct node {
	int t[3][3];
	node () {
		memset(t, 0, sizeof t);
	}
	node operator *(const node &x)const { //循环展开
		node res;
		res.t[1][1] = qm(mul(t[1][1], x.t[1][1]) + mul(t[1][2], x.t[2][1]));
		res.t[1][2] = qm(mul(t[1][1], x.t[1][2]) + mul(t[1][2], x.t[2][2]));
		res.t[2][1] = qm(mul(t[2][1], x.t[1][1]) + mul(t[2][2], x.t[2][1]));
		res.t[2][2] = qm(mul(t[2][1], x.t[1][2]) + mul(t[2][2], x.t[2][2]));
		return res;
	}
};

inline node ksmi(node a, int b) { //矩阵快速幂
	node res;
	res.t[1][1] = res.t[2][2] = 1;
	while (b) {
		if (b & 1) res = res * a;
		a = a * a;
		b >>= 1;
	}
	return res;
}

inline int ksmi(int a, int b) { //普通快速幂
	int res = 1;
	while (b) {
		if (b & 1) res = mul(res, a);
		a = mul(a, a);
		b >>= 1;
	}
	return res;
}

signed main() {
	scanf("%lld%lld", &n, &p);
	if (n == 1) {
		printf("0");
		return 0;
	}
	node A0, A;
	A0.t[1][1] = A0.t[2][1] = 1;
	A.t[1][2] = A.t[2][1] = A.t[2][2] = 1;
	A = ksmi(A, n + 2);
	A0 = A * A0;
	int ans = ksmi(A0.t[1][1] - n - 2, n + 1);
	printf("%lld", ans);
	return 0;
}