P4463 [CTT Mutual Test 2012] calc

A sequence $a_1, a_2, \dots, a_n$ is valid if and only if: - $a_1, a_2, \dots, a_n$ are all integers in $[1, k]$. - $a_1, a_2, \dots, a_n$ are pairwise distinct. The value of a sequence is defined as the product of all its numbers, i.e., $a_1\times a_2\times\dots\times a_n$. Compute the sum of the values of all distinct valid sequences, modulo $p$. Two sequences are different if and only if they differ at any position.

One line with three positive integers $k, n, p$, as described above.

One line with the result.

Constraints For $5\%$ of the testdata, $k \le 10$, $n \le 10$. For $20\%$ of the testdata, $k \le 1000$, $n \le 20$. For $50\%$ of the testdata, $k \le 10^9$, $n \le 20$. For $100\%$ of the testdata, $k \le 10^9$, $n \le 500$, $p \le 10^9$, it is guaranteed that $p$ is prime and $n + 1 < k < p$. by WJMZBMR **** $\mathsf i \color{red}\mathsf{ostream}$ thinks the testdata for this problem is too weak, so he made a [harder version](https://www.luogu.com.cn/problem/P5850). Translated by ChatGPT 5