#include using namespace std; #include using namespace atcoder; using ll = long long; using mint = dynamic_modint<0>; int main() { int n, p; cin >> n >> p; mint::set_mod(p); vector inv(n + 1); inv[1] = 1; for (int i = 2; i <= n; i++) inv[i] = (p - p / i) * inv[p % i]; vector d(n + 1, 0); for (int i = 1; i <= n; i++) for (int j = i; j <= n; j += i) d[j]++; vector sum((int)sqrt(n) + 1, vector()); for (int i = 1; i < sum.size(); i++) sum[i] = vector(n / i + 1, 0); vector dp(n + 1, 0); int sq = 1; for (int k = 3; k <= n; k++) { while ((sq + 1) * (sq + 1) <= k) sq++; mint v = 0; for (int i = 1; i <= k / sq; i++) { if (k % i == 0) continue; v += dp[k / i * i]; } for (int x = 1; x < sq; x++) { int l = k / (x + 1), r = k / x; if (k % x == 0) r--; v += sum[x][r] - sum[x][l]; } v = v * inv[k - d[k]] + k * inv[k - d[k]]; dp[k] = v; for (int x = 1; x * x <= k; x++) if (k % x == 0) sum[x][k / x] = sum[x][k / x - 1] + v; } cout << dp[n].val() << "\n"; }