未来的失败

• 时间限制：3 秒
• 内存限制：256 MiB

题目描述

Alice 与 Bob 在一个字符串上游戏，Alice 先手。字符串长度为 $n$，字符来自前 $k$ 个小写英文字母。

每回合，当前玩家必须执行以下一种操作，并且操作后的字符串不能在本局游戏的此前时刻出现过：

• 任意重排当前字符串；
• 若字符串非空，删除恰好一个字符。

无法执行合法操作的玩家失败。

给定 $n,k$ 和质数 $p$，求长度恰为 $n$、只含前 $k$ 个字母且 Alice 必胜的字符串数量，对 $p$ 取模。

输入格式

一行三个整数 $n,k,p$。

输出格式

输出一个整数，表示答案对 $p$ 取模的结果。

样例输入

4 2 100000007

样例输出

14

样例说明

共有 $14$ 个 Alice 必胜的字符串，例如 bbaa 与 baaa；aaaa 与 bbbb 是败态。

数据范围

对所有数据：$1\le n\le250000$，$1\le k\le26$，$10^8\le p\le10^9+100$，且 $p$ 为质数。

每个测试点独立计分。