#ifdef ONLINE_JUDGE #pragma GCC target("avx2,avx") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #endif #include using namespace std; using ll = long long; using ull = unsigned long long; using i128 = __int128_t; using pii = pair; using pll = pair; #define rep(i, n) for (int i = 0; i < (n); i++) #define all(x) (x).begin(), (x).end() constexpr char ln = '\n'; template inline bool chmax(T1& a, T2 b) { if (a < b) {a = b; return true ;} return false ;} template inline bool chmin(T1& a, T2 b) { if (a > b) {a = b; return true ;} return false ;} struct fast_ios { fast_ios() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_; //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// template struct SquareMatrix { using arr = array; using mat = array; mat A; int N; SquareMatrix() : SquareMatrix(sz) {} SquareMatrix(int N) : N(N) { for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { A[i][j] = 0; } } } int size() { return N; } const arr& operator[](int k) const { return A[k]; } arr& operator[](int k) { return A[k]; } static SquareMatrix add_identity(int N) { return SquareMatrix(N); } static SquareMatrix mul_identity(int N) { SquareMatrix I(N); for(int i = 0; i < N; i++) I[i][i] = 1; return I; } SquareMatrix& operator+=(const SquareMatrix &B) { for(int i = 0; i < N; i++) { for(int j = 0; j < N; j++) { (*this)[i][j] += B[i][j]; } } return *this; } SquareMatrix& operator-=(const SquareMatrix &B) { for(int i = 0; i < N; i++) { for(int j = 0; j < N; j++) { (*this)[i][j] -= B[i][j]; } } return *this; } SquareMatrix& operator*=(const SquareMatrix &B) { SquareMatrix C(N); for(int i = 0; i < N; i++) { for(int k = 0; k < N; k++) { for(int j = 0; j < N; j++) { C[i][j] += (*this)[i][k] * B[k][j]; } } } A.swap(C.A); return *this; } SquareMatrix& operator^=(long long k) { SquareMatrix B = SquareMatrix::mul_identity(N); while(k) { if(k & 1) B *= *this; *this *= *this; k >>= 1; } A.swap(B.A); return *this; } SquareMatrix pow(long long k) { SquareMatrix ret = A; ret ^= k; return ret; } SquareMatrix operator+(const SquareMatrix& B) const { return (SquareMatrix(*this) += B); } SquareMatrix operator-(const SquareMatrix& B) const { return (SquareMatrix(*this) -= B); } SquareMatrix operator*(const SquareMatrix& B) const { return (SquareMatrix(*this) *= B); } SquareMatrix operator^(long long k) const { return (SquareMatrix(*this) ^= k); } bool operator==(const SquareMatrix& B) const { return A == B.A; } bool operator!=(const SquareMatrix& B) const { return A != B.A; } friend ostream& operator<<(ostream& os, SquareMatrix& B) { for(int i = 0; i < B.size(); i++) { os << "["; for(int j = 0; j < B.size(); j++) { os << B[i][j] << (j == B.size()-1 ? "]\n" : ","); } } return os; } }; ///////////////////////////////////////////////////////////////////////////////////// template struct ModInt { public: static constexpr int mod() { return m; } static ModInt raw(int v) { ModInt x; x._v = v; return x; } ModInt() : _v(0) {} ModInt(long long v) { long long x = (long long)(v % (long long)(umod())); if (x < 0) x += umod(); _v = (unsigned int)(x); } unsigned int val() const { return _v; } ModInt& operator++() { _v++; if (_v == umod()) _v = 0; return *this; } ModInt& operator--() { if (_v == 0) _v = umod(); _v--; return *this; } ModInt operator++(int) { ModInt result = *this; ++*this; return result; } ModInt operator--(int) { ModInt result = *this; --*this; return result; } ModInt& operator+=(const ModInt& rhs) { _v += rhs._v; if (_v >= umod()) _v -= umod(); return *this; } ModInt& operator-=(const ModInt& rhs) { _v -= rhs._v; if (_v >= umod()) _v += umod(); return *this; } ModInt& operator*=(const ModInt& rhs) { unsigned long long z = _v; z *= rhs._v; _v = (unsigned int)(z % umod()); return *this; } ModInt& operator^=(long long n) { ModInt x = *this; *this = 1; if (n < 0) x = x.inv(), n = -n; while (n) { if (n & 1) *this *= x; x *= x; n >>= 1; } return *this; } ModInt& operator/=(const ModInt& rhs) { return *this = *this * rhs.inv(); } ModInt operator+() const { return *this; } ModInt operator-() const { return ModInt() - *this; } ModInt pow(long long n) const { ModInt r = *this; r ^= n; return r; } ModInt inv() const { int a = _v, b = umod(), y = 1, z = 0, t; for (; ; ) { t = a / b; a -= t * b; if (a == 0) { assert(b == 1 || b == -1); return ModInt(b * z); } y -= t * z; t = b / a; b -= t * a; if (b == 0) { assert(a == 1 || a == -1); return ModInt(a * y); } z -= t * y; } } friend ModInt operator+(const ModInt& lhs, const ModInt& rhs) { return ModInt(lhs) += rhs; } friend ModInt operator-(const ModInt& lhs, const ModInt& rhs) { return ModInt(lhs) -= rhs; } friend ModInt operator*(const ModInt& lhs, const ModInt& rhs) { return ModInt(lhs) *= rhs; } friend ModInt operator/(const ModInt& lhs, const ModInt& rhs) { return ModInt(lhs) /= rhs; } friend ModInt operator^(const ModInt& lhs, long long rhs) { return ModInt(lhs) ^= rhs; } friend bool operator==(const ModInt& lhs, const ModInt& rhs) { return lhs._v == rhs._v; } friend bool operator!=(const ModInt& lhs, const ModInt& rhs) { return lhs._v != rhs._v; } friend ModInt operator+(long long lhs, const ModInt& rhs) { return (ModInt(lhs) += rhs); } friend ModInt operator-(long long lhs, const ModInt& rhs) { return (ModInt(lhs) -= rhs); } friend ModInt operator*(long long lhs, const ModInt& rhs) { return (ModInt(lhs) *= rhs); } friend ostream &operator<<(ostream& os, const ModInt& rhs) { return os << rhs._v; } private: unsigned int _v; static constexpr unsigned int umod() { return m; } }; static int MOD; using mint = ModInt; void yuki526() { long long N; cin >> N >> MOD; SquareMatrix mat(2); mat[0][0] = mat[0][1] = mat[1][0] = 1; mat ^= N-1; cout << mat[1][0] << endl; } int main() { yuki526(); } /* verified on 2020/10/10 https://yukicoder.me/problems/no/526 */