CF838C.Future Failure

Alice and Bob are playing a game with a string of characters, with Alice going first. The string consists n characters, each of which is one of the first k letters of the alphabet. On a player’s turn, they can either arbitrarily permute the characters in the words, or delete exactly one character in the word (if there is at least one character). In addition, their resulting word cannot have appeared before throughout the entire game. The player unable to make a valid move loses the game.

Given n, k, p, find the number of words with exactly n characters consisting of the first k letters of the alphabet such that Alice will win if both Alice and Bob play optimally. Return this number modulo the prime number p.

爱丽丝和鲍勃正在用一个字符字符串进行一场游戏，爱丽丝先手。该字符串由 n 个字符组成，每个字符均为字母表前 k 个字母之一。在一名玩家的回合中，其可以执行以下两种操作之一：

• 任意重排字符串中所有字符的顺序；
• 或者（当字符串至少包含一个字符时）恰好删除一个字符。

此外，操作后得到的新字符串在整个游戏过程中不得曾出现过。无法进行合法操作的玩家判负。

给定 n, k, p，求满足以下条件的字符串个数：该字符串长度恰好为 n，且仅由字母表前 k 个字母构成，并且在双方均采取最优策略的情况下爱丽丝必胜。将该数目对素数 p 取模后返回。

The first line of input will contain three integers n, k, p (1 ≤ n ≤ 250 000, 1 ≤ k ≤ 26, 108 ≤ p ≤ 109 + 100, p will be prime).

输入的第一行包含三个整数 $n$、$k$、$p$（$1 \leq n \leq 250\,000$，$1 \leq k \leq 26$，$10^8 \leq p \leq 10^9 + 100$，且 $p$ 为质数）。

Print a single integer, the number of winning words for Alice, modulo p.

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

There are 14 strings that that Alice can win with. For example, some strings are "bbaa" and "baaa". Alice will lose on strings like "aaaa" or "bbbb".

有 14 个字符串使得 Alice 获胜。例如，部分字符串为 “bbaa” 和 “baaa”。Alice 在诸如 “aaaa” 或 “bbbb” 这样的字符串上会失败。