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_.
## Input
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).
## Output
Print a single integer, the number of winning words for Alice, modulo _p_.
[samples]
## Note
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".
Alice 和 Bob 正在玩一个涉及字符串的游戏，Alice 先手。字符串由 #cf_span[n] 个字符组成，每个字符是字母表前 #cf_span[k] 个字母之一。在一名玩家的回合中，他们可以任意重排字符串中的字符，或恰好删除一个字符（如果至少有一个字符）。此外，他们得到的新字符串在整个游戏中不能之前出现过。无法进行有效移动的玩家输掉游戏。
给定 #cf_span[n, k, p]，求由字母表前 #cf_span[k] 个字母组成的、恰好包含 #cf_span[n] 个字符的字符串中，有多少个字符串使得 Alice 在双方均采取最优策略时获胜。请将结果对质数 #cf_span[p] 取模。
输入的第一行包含三个整数 #cf_span[n, k, p]（#cf_span[1 ≤ n ≤ 250 000]，#cf_span[1 ≤ k ≤ 26]，#cf_span[108 ≤ p ≤ 109 + 100]，#cf_span[p] 为质数）。
输出一个整数，表示 Alice 的获胜字符串数量，对 #cf_span[p] 取模。
共有 14 个字符串使得 Alice 可以获胜。例如，一些字符串是 "bbaa" 和 "baaa"。Alice 在 "aaaa" 或 "bbbb" 这样的字符串上会输。
## Input
输入的第一行包含三个整数 #cf_span[n, k, p]（#cf_span[1 ≤ n ≤ 250 000]，#cf_span[1 ≤ k ≤ 26]，#cf_span[108 ≤ p ≤ 109 + 100]，#cf_span[p] 为质数）。
## Output
输出一个整数，表示 Alice 的获胜字符串数量，对 #cf_span[p] 取模。
[samples]
## Note
共有 14 个字符串使得 Alice 可以获胜。例如，一些字符串是 "bbaa" 和 "baaa"。Alice 在 "aaaa" 或 "bbbb" 这样的字符串上会输。
**Definitions**
Let $ \Sigma_k = \{1, 2, \dots, k\} $ be the alphabet of size $ k $.
Let $ S_{n,k} $ be the set of all strings of length $ n $ over $ \Sigma_k $, so $ |S_{n,k}| = k^n $.
Each string $ w \in S_{n,k} $ is represented by its frequency vector $ \mathbf{f} = (f_1, f_2, \dots, f_k) \in \mathbb{N}^k $, where $ f_i $ is the count of character $ i $ in $ w $, and $ \sum_{i=1}^k f_i = n $.
**Game Rules**
A move consists of one of the following:
1. **Permute**: Replace the current string with any anagram of it (i.e., any string with the same frequency vector).
2. **Delete**: Replace the current string with a string obtained by deleting exactly one character (i.e., reduce one $ f_i $ by 1, provided $ f_i \geq 1 $).
A position (string) is **invalid** if it has appeared earlier in the game.
The game starts from the initial string; players alternate turns; the player unable to move loses.
**Key Insight**
Since permutations do not change the frequency vector, the game state is fully determined by the multiset of character counts — i.e., the frequency vector $ \mathbf{f} $.
Thus, the game is equivalent to a state space over the set of frequency vectors $ \mathbf{f} \in \mathbb{N}^k $ with $ \|\mathbf{f}\|_1 = n $, where:
- From $ \mathbf{f} $, a player can move to:
- Any $ \mathbf{f}' $ with the same multiset of counts (permutation — **no new state**),
- Or any $ \mathbf{f}' $ such that $ \mathbf{f}' = \mathbf{f} - \mathbf{e}_i $ for some $ i $ with $ f_i \geq 1 $ (deletion — **new state**).
Since permutations do not produce new states (they are equivalent under the rules), the **only transitions** that matter are deletions reducing one count by 1.
Thus, the game reduces to a **directed acyclic graph** on frequency vectors, with edges from $ \mathbf{f} $ to $ \mathbf{f} - \mathbf{e}_i $ for all $ i $ with $ f_i > 0 $.
The game starts at a given $ \mathbf{f} $, and players alternately move along edges (deleting one character).
The first player to face the zero vector $ \mathbf{0} $ loses (no moves left).
**Note**: The condition "cannot have appeared before" implies that once a frequency vector is used, it cannot be reused. But since permutations are equivalent, and deletion strictly reduces the total length, **each frequency vector is visited at most once**.
Thus, the game is equivalent to a **impartial game on the poset of frequency vectors** under component-wise $ \leq $, with moves decreasing one coordinate by 1.
This is equivalent to a **disjunctive game** of $ k $ independent piles of sizes $ f_1, f_2, \dots, f_k $, where each move reduces one pile by 1.
This is **exactly** the game of **Nim with $ k $ piles of sizes $ f_1, \dots, f_k $**.
**Standard Result**:
In Nim, the winning condition is determined by the **Nim-sum** (XOR of pile sizes).
- Position is losing (P-position) iff $ f_1 \oplus f_2 \oplus \cdots \oplus f_k = 0 $.
- Otherwise, it is winning (N-position).
Thus, Alice wins if and only if the Nim-sum of the character frequencies is **non-zero**.
**Objective**
Count the number of strings $ w \in S_{n,k} $ (i.e., frequency vectors $ \mathbf{f} \in \mathbb{N}^k $, $ \sum f_i = n $) such that
$$
f_1 \oplus f_2 \oplus \cdots \oplus f_k \neq 0
$$
modulo prime $ p $.
Equivalently:
$$
\text{Answer} = k^n - \#\left\{ \mathbf{f} \in \mathbb{N}^k : \sum_{i=1}^k f_i = n \text{ and } \bigoplus_{i=1}^k f_i = 0 \right\} \mod p
$$
**Final Formal Statement**
**Definitions**
Let $ \mathcal{F}_{n,k} = \left\{ \mathbf{f} = (f_1, \dots, f_k) \in \mathbb{N}^k : \sum_{i=1}^k f_i = n \right\} $.
Let $ \oplus(\mathbf{f}) = f_1 \oplus f_2 \oplus \cdots \oplus f_k $ denote the bitwise XOR of the components.
**Constraints**
- $ 1 \leq n \leq 250{,}000 $
- $ 1 \leq k \leq 26 $
- $ 10^8 \leq p \leq 10^9 + 100 $, $ p $ prime
**Objective**
Compute:
$$
\left( k^n - \left| \left\{ \mathbf{f} \in \mathcal{F}_{n,k} : \oplus(\mathbf{f}) = 0 \right\} \right| \right) \mod p
$$