#include #include #include #include int main() { std::cin.tie(nullptr)->sync_with_stdio(false); int N, M, P; std::cin >> N >> M >> P; std::vector F(N + 1, 1), invF(N + 1); for (int i{1} ; i <= N ; i++) F[i] = (F[i - 1] * i) % P; invF[N] = [&](){ // P - 2δΉ— long long res{1}, cur{F[N]}; int exp{P - 2}; while (exp) { if (exp & 1) res = res * cur % P; cur = cur * cur % P; exp >>= 1; } return res; }(); for (int i{N} ; i >= 1 ; i--) invF[i - 1] = invF[i] * i % P; 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{(((F[M] * invF[i]) % P) * invF[M - i]) % P}; ans += dp[j] * comb; ans %= P; } if (i == M) break; std::vector sum(N + 2); for (int i{} ; i < N + 1 ; i++) sum[i + 1] = (sum[i] + dp[i]) % P; std::vector next(N + 1); for (int j{1} ; j <= N ; j++) next[j] = (j * sum[j]) % P; dp = std::move(next); } ans *= F[N - M]; ans %= P; ans *= invF[N]; ans %= P; std::cout << ans << '\n'; }