#include #include #include #include using namespace __gnu_pbds; template using Tree=tree,rb_tree_tag,tree_order_statistics_node_update>; template struct matrix{ public: using value_type = T; private: std::vector> mat; int row, col; public: matrix() = default; matrix(int n) : matrix(n, n) {} matrix(int m, int n) : mat(m, std::vector(n)), row(m), col(n) {} constexpr matrix operator+(const matrix rhs) const { return matrix(*this) += rhs; } constexpr matrix operator-(const matrix rhs) const { return matrix(*this) -= rhs; } constexpr matrix operator*(const matrix rhs) const { return matrix(*this) *= rhs; } constexpr matrix &operator+=(const matrix rhs) { static_assert(!mat.empty() && mat.row == rhs.row && mat.col == rhs.col); for (int i = 0; i < row; ++i) { for (int j = 0; j < col; ++j) { mat[i][j] += rhs.mat[i][j]; } } } constexpr matrix &operator-=(const matrix rhs) { static_assert(!mat.empty() && row == rhs.row && col == rhs.col); for (int i = 0; i < row; ++i) { for (int j = 0; j < col; ++j) { mat[i][j] -= rhs.mat[i][j]; } } } constexpr matrix operator*(const value_type a) const noexcept { return matrix(*this) *= a; } constexpr matrix operator*=(const value_type a) noexcept { for (int i = 0; i < row; ++i) { for (int j = 0; j < col; ++j) { mat[i][j] *= a; } } return *this; } constexpr bool operator==(const matrix rhs) const noexcept { if (row != rhs.row || col != rhs.col) return false; for (int i = 0; i < row; ++i) { for (int j = 0; j < col; ++j) { if (mat[i][j] != rhs.mat[i][j]) return false; } } return true; } constexpr bool operator!=(const matrix rhs) const noexcept { return !(matrix(*this) == rhs); } constexpr std::vector &operator[](int pos) { return mat[pos]; } constexpr matrix mul(const matrix lhs, const matrix rhs) const { assert(lhs.col == rhs.row); matrix res(lhs.row, rhs.col); for (int i = 0; i < lhs.row; ++i) { for (int k = 0; k < rhs.col; ++k) { for (int j = 0; j < lhs.col; ++j) { res.mat[i][j] += lhs.mat[i][k] * rhs.mat[k][j]; } } } return res; } constexpr matrix pow(matrix x, long long n) { int len = x.row; matrix res(len, len), a = x; for (int i = 0; i < len; ++i) { res[i][i] = 1; } while (n) { if (n & 1) res = mul(res, a); a = mul(a, a); n >>= 1; } return res; } constexpr int height() const { return row; } constexpr int width() const { return col; } friend std::ostream &operator<<(std::ostream &os, matrix &x) { for (int i = 0; i < x.row; ++i) { for (int j = 0; j < x.col; ++j) { os << x.mat[i][j] << (j + 1 == x.col ? "\n" : " "); } } return os; } }; struct arbmodint{ private: long long x; static long long &mod() { static long long mod_ = 0; return mod_; } public: arbmodint(const long long v = 0) { x = v; if (x >= get_mod()) x += get_mod(); if (x < 0) x = x % get_mod() + get_mod(); } static void set_mod(const long long m) { mod() = m; } static long long get_mod() { return mod(); } long long &val() noexcept { return x; } friend std::ostream &operator<<(std::ostream& os, arbmodint& b) { return os << b.x; } friend std::istream &operator>>(std::istream& is, arbmodint& b) { return is >> b.x; } arbmodint operator+(const arbmodint rhs) const { return arbmodint(*this) += rhs; } arbmodint operator-(const arbmodint rhs) const { return arbmodint(*this) -= rhs; } arbmodint operator*(const arbmodint rhs) const { return arbmodint(*this) *= rhs; } arbmodint operator/(const arbmodint rhs) const { return arbmodint(*this) /= rhs; } arbmodint &operator+=(const arbmodint rhs) { x += rhs.x; if(x >= get_mod()) x -= get_mod(); return *this; } arbmodint &operator-=(const arbmodint rhs) { if (x < rhs.x) x += get_mod(); x -= rhs.x; return *this; } arbmodint &operator*=(const arbmodint rhs) { x = x * rhs.x % get_mod(); return *this; } arbmodint &operator/=(const arbmodint rhs) { return *this = *this * rhs.inv(); } arbmodint inv() const { long long a = x, b = get_mod(), u = 1, v = 0, t; while (b) { t = a / b; a -= t * b; u -= t * v; std::swap(a, b); std::swap(u, v); } u %= get_mod(); if (u < 0) u += get_mod(); return u; } arbmodint pow(long long n) const { arbmodint a = *this, res = 1; while (n) { if (n & 1) res *= a; a *= a; n >>= 1; } return res; } }; using mint=arbmodint; int main() { long long n,m; std::cin >>n >>m; mint::set_mod(m); matrix f(2,2); f[0][0]=f[0][1]=f[1][0]=mint(1); f=f.pow(f,n-2); std::cout <