#include #include #include using ll = long long; using namespace std; using Matrix = vector>; ll MOD; Matrix mul(const Matrix& a, const Matrix& b) { assert(a[0].size() == b.size()); ll n, m, l; n = a.size(); m = b[0].size(); l = a[0].size(); Matrix c(n, vector(m, 0)); for (ll i = 0; i < n; i++) { for (ll k = 0; k < l; k++) { for (ll j = 0; j < m; j++) { c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % MOD; } } } return c; } Matrix matpow(Matrix a, ll n) { if (n == 0) { ll s = a.size(); Matrix b(s, vector(s, 0)); for (ll i = 0; i < s; i++) b[i][i] = 1; return b; } Matrix temp = matpow(a, n/2); if (n & 1) return mul(mul(temp, temp), a); else return mul(temp, temp); } int main() { // ll n = 281621358815590; // MOD = 30524; ll n; cin >> n; cin >> MOD; Matrix a(2, vector(2, 0)); a[0][0] = 1; a[0][1] = 1; a[1][0] = 1; a[1][1] = 0; a = matpow(a, n); Matrix x(2, vector(1, 0)); x[0][0] = 1; x[1][0] = 0; x = mul(a, x); // cout << x[0][0] << " " << x[1][0] << endl; cout << x[1][0] << endl; }