CF838C Future Failure

Alice 和 Bob 正在玩一个字符串游戏，Alice 先手。该字符串有 $n$ 个字符，每个字符都是前 $k$ 个英文字母之一。在每位玩家的回合，他们可以选择对单词中的字符进行任意重排，或者删除单词中的恰好一个字符（如果单词里还有字符）。另外，在整个游戏过程中，已经出现过的单词不能再次出现。无法进行有效操作的玩家判负。 给定 $n,k,p$，求由前 $k$ 个字母组成的、长度恰为 $n$ 的单词中，有多少种单词使得 Alice 在两人都采取最优策略时最终能获胜。请将答案对质数 $p$ 取模后输出。

输入一行包含三个整数 $n,k,p$（$1\leq n\leq 250000$，$1\leq k\leq 26$，$10^{8}\leq p\leq 10^{9}+100$，$p$ 是质数）。

输出一个整数，表示 Alice 能获胜的单词数量，对 $p$ 取模。

有 14 个字符串 Alice 能获胜。例如，"bbaa"、"baaa" 都是这样的字符串。Alice 会输掉像 "aaaa" 或 "bbbb" 这样的字符串。 由 ChatGPT 5 翻译