#include<bits/stdc++.h>
#define pb emplace_back
#define AI(i) begin(i), end(i)
using namespace std;
using ll = long long;
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() {cerr << endl;}
template<class T, class ...U> void kout (T v, U ...e) { cerr << v << ' ', kout(e...); }
template<class T> void debug(T L, T R) { while (L != R) cerr << *L << " \n"[next(L)==R], ++L; }
#else
#define DE(...) 0
#define debug(...) 0
#endif
// What I should check
// 1. overflow
// 2. corner cases
// Enjoy the problem instead of hurrying to AC
// Good luck !
const int MAX_N = 7510;

/*
ID: ckevin31
LANG: C++14
TASK:
*/
#ifndef KEV
inline void IO(string name) { freopen((name +  ".in").c_str(), "r", stdin); freopen((name + ".out").c_str(), "w", stdout); }
#else
#define IO(...) 0
#endif

int N, mod;

bool notp[MAX_N];
int pri[MAX_N], pl;

struct FastMod {
    ll mod;
    FastMod(const ll v = 2) : mod(v) {}
    ll operator()(ll v) { return v % mod; }
}FM;
//struct FastMod {
//  uint64_t b, m;
//  FastMod(uint64_t b = 1) : b(b), m(uint64_t((__uint128_t(1) << 64) / b)) {}
//  uint64_t operator()(uint64_t a) {
//      return a % b;
//      uint64_t q = (uint64_t)((__uint128_t(m) * a) >> 64);
//      uint64_t r = a - q * b; // can be proven that 0 <= r < 2*b
//      return r >= b ? r - b : r;
//  }
//}FM;
struct mint {
    ll v;
    mint () : v(0) {}
    mint (int v) : v(v) {}
    mint (ll v) : v(v) {}
    mint (uint64_t v) : v(v) {}
};

mint operator + (mint a, mint b) { return FM(a.v + b.v); }
//mint operator + (mint a, mint b) { a.v += b.v - mod; a.v += (a.v >> 63) & mod; return a; }
mint& operator += (mint &a, mint b) { return a = a + b; }
mint operator - (mint a, mint b) { return FM(a.v - b.v + mod); }
//mint operator - (mint a, mint b) { a.v += b.v; a.v += (a.v >> 63) & mod; return a; }
mint& operator -= (mint &a, mint b) { return a = a - b; }
mint operator * (mint a, mint b) { return FM(a.v * b.v); }
mint& operator *= (mint &a, mint b) { return a = a * b; }
bool operator == (mint a, mint b) { return a.v == b.v; }
ostream& operator << (ostream& out, mint a) { return out << a.v ; }

mint bin_pow(mint v, ll t) {
    mint res = 1;
    for (;t;t>>=1, v *= v)
        if (t&1) res *= v;
    return res;
}
mint getinv(mint v) { return bin_pow(v, mod-2); }

mint operator / (mint a, mint b) { return a.v * getinv(b.v); }

mint fa[MAX_N], inv[MAX_N], fai[MAX_N];

void init() {
    for (int i = 0;i < 2;++i)
        fa[i] = inv[i] = fai[i] = 1;
    for (int i = 2;i <= N;++i) {
        fa[i] = fa[i-1] * i;
        inv[i] = (mod - mod / i) * inv[mod % i];
        fai[i] = inv[i] * fai[i-1];
    }
}
mint C(int N, int M) { return N < M ? 0 : fa[N] * fai[M] * fai[N-M]; }

mint dp[MAX_N];

void getdp() {
    dp[0] = 1;
    for (int i = 1;i <= N;++i) {
        for (int j = N;j >= 0;--j) {
            mint dn = 1;
            for (int len = i, cnt = 1; j + len <= N; len += i, ++cnt) {
                dn *= i * cnt;
                dp[j + len] +=
                    dp[j] * C(j + len, len) * fa[len] / dn;
            }
        }
    }
    assert(dp[N] == fa[N]);
}
mint calnot(int val) {
    for (int i = val;i <= N;++i) {
        if (i % val) continue;
        for (int j = 0;j <= N;++j) {
            mint dn = 1;
            for (int len = i, cnt = 1; j + len <= N; len += i, ++cnt) {
                dn *= i * cnt;
                dp[j + len] -=
                    dp[j] * C(j + len, len) * fa[len] / dn;
            }
        }
    }
    mint res = dp[N];
    for (int i = 1;i <= N;++i) {
        if (i % val) continue;
        for (int j = N;j >= 0;--j) {
            mint dn = 1;
            for (int len = i, cnt = 1; j + len <= N; len += i, ++cnt) {
                dn *= i * cnt;
                dp[j + len] +=
                    dp[j] * C(j + len, len) * fa[len] / dn;
            }
        }
    }
    return res;
}
int32_t main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    IO("exercise");

    cin >> N >> mod;

    FM = FastMod(mod);

    init();
    getdp();

    mint res = 1;

    for (int i = 2;i <= N;++i) if (!notp[i]) {
        pri[pl++] = i;
        for (int j = i + i;j <= N;j += i)
            notp[j] = true;

        int v = i;
        while (v <= N) {
            mint way = calnot(v * i) - calnot(v);
            assert(way.v >= 0);
            DE(v, way);
            res *= bin_pow(v, way.v);
            v *= i;
        }
    }

    cout << res << '\n';
}