Description

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.

Input Format

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

Output Format

One line with the result.

9 7 10007

3611

Hint

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.

Translated by ChatGPT 5