rt，斐波那契第n项的板子

//#pragma GCC optimize(3,"Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native")
#include <bits/stdc++.h>
#define JS ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
using namespace std;

struct Matrix {
	int m[3][3];
};
Matrix a1, a2;
int n, m;

Matrix mat_mul(Matrix x, Matrix y) {
	Matrix res;
	memset(res.m, 0, sizeof(res.m));
	for (int i = 1; i <= 2; i++) {
		for (int j = 1; j <= 2; j++) {
			for (int k = 1; k <= 2; k++) {
				res.m[i][j] = (res.m[i][j] + (x.m[i][k] % m) * (y.m[k][j] % m)) % m;
			}
		}
	}
	return res;
}

Matrix mat_pow(int x) {
	Matrix t1, t2;
	t1.m[1][1] = 1, t1.m[1][2] = 0, t1.m[2][1] = 0, t1.m[2][2] = 1;
	t2.m[1][1] = 1, t2.m[1][2] = 1, t2.m[2][1] = 1, t2.m[2][2] = 0;
	while (x) {
		if (x & 1) {
			t1 = mat_mul(t1, t2);
		}
		x >>= 1, t2 = mat_mul(t2, t2);
	}
	return t1;
}

int main() {
	JS;
	cin >> n >> m;
	Matrix ans;
	ans = mat_pow(n - 1);
	cout << ans.m[1][1];
	return 0;
}