calc

一个序列 $a_1, a_2, \ldots, a_n$ 是合法的，当且仅当：

• 长度为给定的 $n$；
• $a_1, a_2, \ldots, a_n$ 都是 $[1, A]$ 中的整数；
• $a_1, a_2, \ldots, a_n$ 互不相等。

一个序列的值定义为它里面所有数的乘积，即 $a_1a_2\cdots a_n$。

请求出所有不同合法序列的值的和。两个序列不同，当且仅当它们存在某一位不一样。

输出答案对 $\mathit{mod}$ 取余的结果。

输入格式

一行 $3$ 个数 $A, n, \mathit{mod}$，意义如上所述。

输出格式

一行一个结果。

样例输入

9 7 10007

样例输出

3611

数据范围

• 测试点 $0$：$A\le 10$，$n\le 10$；
• 测试点 $1\sim 3$：$A\le 1000$，$n\le 20$；
• 测试点 $4\sim 9$：$A\le 10^9$，$n\le 20$；
• 测试点 $10\sim 19$：$A\le 10^9$，$n\le 500$。

对于全部数据，$\mathit{mod}\le 10^9$，且 $\mathit{mod}$ 为素数，$\mathit{mod}>A>n+1$。

来源与许可

本题题面与测试数据整理自 BZOJ 2655。

样例 1

输入

9 7 10007

输出

3611