#include using namespace std; // 行列の積を計算する関数 vector> matrixMultiply(const vector>& a, const vector>& b, long long m) { int size = a.size(); vector> result(size, vector(size, 0)); for (int i = 0; i < size; ++i) { for (int j = 0; j < size; ++j) { for (int k = 0; k < size; ++k) { result[i][j] = (result[i][j] + (a[i][k] * b[k][j]) % m) % m; } } } return result; } // 行列のべき乗を計算する関数(繰り返し二乗法) vector> matrixPower(vector> base, long long n, long long m) { int size = base.size(); vector> result(size, vector(size)); for(int i=0; i < size; i++){ result[i][i] = 1; } while (n > 0) { if (n & 1) { // nが奇数の場合 result = matrixMultiply(result, base, m); } base = matrixMultiply(base, base, m); n >>= 1; // n を 2 で割る } return result; } int main() { long long n, m; cin >> n >> m; if (n == 0) { cout << 0 << endl; return 0; } if(n == 1) { cout << 1 << endl; return 0; } // 行列 A を定義 vector> base = {{1, 1}, {1, 0}}; // A の n-1 乗を計算 vector> result_matrix = matrixPower(base, n - 1, m); // F(n) を計算 long long fib_n = result_matrix[0][0]; cout << fib_n << endl; return 0; }