[集训队互测2012] calc

题目描述

一个序列 $ a_1,a_2,\dots,a_n$ 是合法的,当且仅当: 长度为给定的 $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$ 取余的结果。

输入输出格式

输入格式


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

输出格式


一行结果。

输入输出样例

输入样例 #1

9 7 10007

输出样例 #1

3611

说明

0:$k \le 10,n \le 10$。 1..3:$k \le 1000,n \le 20$. 4..9:$k \le 10^9,n \le 20$ 10..19:$k \le 10^9,n \le 500$。 全部: $p \le 10^9$,并且 $p$ 为素数,$p>k>n+1$ by WJMZBMR **** $\mathsf i \color{red}\mathsf{ostream}$ 觉得这题数据太弱了,于是他造了个[加强版](https://www.luogu.com.cn/problem/P5850)