[集训队互测 2012] calc

一个序列 $a_1,a_2,\dots,a_n$ 是合法的，当且仅当： - $a_1,a_2,\dots,a_n$ 都是 $[1,k]$ 中的整数。 - $a_1,a_2,\dots,a_n$ 互不相等。 一个序列的值定义为它里面所有数的乘积，即 $a_1\times a_2\times\dots\times a_n$。 求所有不同合法序列的值的和对 $p$ 取模后的结果。两个序列不同当且仅当他们任意一位不同。

一行三个正整数 $k, n, p$。意义为上面所说的。

一行结果。

9 7 10007

3611

【数据范围】 对于 $5\%$ 的数据，$k \le 10$，$n \le 10$。 对于 $20\%$ 的数据，$k \le 1000$，$n \le 20$。 对于 $50\%$ 的数据，$k \le 10^9$，$n \le 20$。 对于 $100\%$ 的数据，$k \le 10 ^ 9$，$n \le 500$，$p \le 10 ^ 9$，保证 $p$ 为素数，保证 $n + 1 < k < p$。 by WJMZBMR **** $\mathsf i \color{red}\mathsf{ostream}$ 觉得这题数据太弱了，于是他造了个[加强版](https://www.luogu.com.cn/problem/P5850)