// 頼む!!!通れ!! #include #include #include #include #include int N, M, P; long long add(long long L, long long R) { assert(0 <= L and L < P); assert(0 <= R and R < P); L += R; if (L >= P) L -= P; return L; } long long mult(long long L, long long R) { assert(0 <= L and L < P); assert(0 <= R and R < P); return (L * R) % P; } long long pow(long long A, long long exp) { long long res{1 % P}; A %= P; while (exp) { if (exp & 1) res = mult(res, A); A = mult(A, A); exp >>= 1; } return res; } long long inv_mult(long long v) { assert(0 <= v and v < P); return pow(v, P - 2); } long long divm(long long L, long long R) { assert(0 <= L and L < P); assert(0 <= R and R < P); return mult(L, inv_mult(R)); } long long solve() { std::vector F(N + 1, 1), invF(N + 1); for (int i{1} ; i <= N ; i++) F[i] = mult(F[i - 1], i); invF[N] = inv_mult(F[N]); for (int i{N} ; i >= 1 ; i--) invF[i - 1] = mult(invF[i], i); std::vector dp(N + 1); for (int i{1} ; i <= N ; i++) dp[i] = i; long long ans{}; for (int i{1} ; i <= M ; i++) { for (int j{1} ; j <= N ; j++) { long long comb{mult(F[M], mult(invF[i], invF[M - i]))}; // P(N - i, M - i)だわ。アホすぎた comb = mult(comb, mult(F[N - i], invF[(N - i) - (M - i)])); ans = add(ans, mult(dp[j], comb)); } if (i == M) break; std::vector sum(N + 2); for (int j{} ; j < N + 1 ; j++) sum[j + 1] = add(sum[j], dp[j]); std::vector next(N + 1); for (int j{1} ; j <= N ; j++) next[j] = mult(j, sum[j]); dp = std::move(next); } ans = mult(ans, F[N - M]); ans = mult(ans, invF[N]); return ans; } long long brute() { std::vector cur; auto dfs{[&](auto dfs, int i) -> long long { if (i == N or (int)cur.size() == M) { if (cur.empty()) return 0LL; long long res{1}; for (auto c : cur) res = mult(res, c); // binom(M, cur.size()) for (int i{} ; i < (int)cur.size() ; i++) { res = mult(res, M - i); res = divm(res, i + 1); } return res; } else { long long res{}; res = add(res, dfs(dfs, i + 1)); if (cur.size() < (size_t)M) { cur.push_back(i + 1); res = add(res, dfs(dfs, i + 1)); cur.pop_back(); } return res; } }}; return dfs(dfs, 0); } #include int main() { std::cin.tie(nullptr)->sync_with_stdio(false); // std::mt19937 mt{std::random_device{}()}; std::cin >> N >> M >> P; std::cout << solve() << '\n'; // while (true) { // // std::cin >> N >> M >> P; // N = mt() % 20 + 1; // M = mt() % 20 + 1; // if (N < M) std::swap(N, M); // P = 23; // long long a{solve()}, b{brute()}; // if (a != b){ // std::cout << N << ' ' << M << ' ' << P << std::endl; // std::cout << a << ' ' << b << std::endl; // std::exit(0); // } // // std::cout << brute() << '\n'; // // std::cout << solve() << '\n'; // } }