暂无测试数据。

题目描述

~~在学校上课很无聊，为了偷偷摸鱼，~~蒜头君和花椰妹决定玩个游戏。

蒜头君 和 花椰妹 正在玩游戏，游戏规则如下——作为裁判的 Bandiaoz 指定一个长度为 $n(1 \leq n \leq 266666)$，字符集大小为 $k(1 \leq k \leq 266666)$ 的字符串，每次操作，当前操作者可以选择一下两种操作之一：

• 从当前字符删去一个字符
• 重新组合当前字符串中的字符，使得新字符串此前没有出现过

可以看出，这个游戏总会在有限步后结束，率先把字符串删完的人获胜，蒜头君 先手，蒜头君和 花椰妹 都是绝顶聪明的（即他们会按照最优策略操作）。

和大家都一样，Bandiaoz 也喜欢 蒜头君，所以他想让 蒜头君 赢。给定 $n,k$，Bandiaoz 想知道有多少种符合条件的字符串可以使得 蒜头君 获胜（假设字符集为 $\{1,2,....k\}$），由于答案过于巨大，所以 Bandiaoz 请你将答案模 $p$ 输出。

输入格式

一行三个空格分隔的正整数 $n,k,p$，分别表示字符串长度，字符集大小和模数。

输出格式

一行一个数字表示能够使 蒜头君 获胜的字符串数量 mod $p$ 的值。

数据范围

对于 $10\%$ 的数据，$1 \leq n,k \leq 3$

对于 $20\%$ 的数据，$1 \leq n,k \leq 8$

对于另外 $15\%$ 的数据，$n$ 为奇数

对于另外 $10\%$ 的数据，$1 \leq k \leq 10$

对于再另外 $10\%$ 的数据，$1 \leq n \leq 66666$

对于 $65\%$ 的数据，$1 \leq k \leq 10,1 \leq n \leq 66666$；
对于 $100\%$ 的数据，$1 \leq n,k \leq 266666,10^7 \leq p \leq 10^9+9$，$p$为质数，数据有梯度。

4 2 998244353

14

1926 817 19260817

13526338