Problem Description

Kujou Sara is a girl who loves creating problems.

Although creating problems is a lot of fun, making them into official contests is not so enjoyable: generating data always wears one out.

In ZJOI2018 Day 1, Sara came up with a very interesting problem related to trees. She decided to use a common method to randomly generate a rooted tree with $n$ nodes:

• Node 1 is the root of the tree.
• For $i \in [2, n]$, independently select a node from $[1, i)$ with equal probability to be the parent of $i$.

Sara doesn't want to consider whether such randomly generated data can defeat brute force solutions, as heuristic methods are also part of the OI competition.

Sara is more concerned about the problem's differentiation and whether all possible scores appear. Therefore, she hopes that any two test cases' trees are distinct: this way, there might be incorrect programs that can pass only one of the cases.

Thus, Sara wants to calculate the probability that, by independently generating $k$ rooted trees $T_1$ to $T_k$ with $n$ nodes each using the above method, any two of them are isomorphic.

Two rooted trees $T_1$ and $T_2$ with $n$ nodes are isomorphic if and only if there exists a permutation $p$ of length $n$ such that $p_1 = 1$ and for $\forall i \in [2, n]$, if $i$ has parent $f$ in $T_1$, then $p_i$ has parent $p_f$ in $T_2$.

Input Format

The first line contains three integers $n$, $k$, and $p$, representing the number of nodes, the number of trees, and the modulus, respectively. It is guaranteed that $10^8 \leq p \leq 10^9$ and $p$ is a prime number.

Output Format

Output a single integer, which is the answer modulo $p$. That is, if the answer in its simplest fractional form is $\frac{a}{b}$, output $a \times b^{-1} \bmod p$.

Sample Input and Output

Input Sample #1

2 2 998244353

Output Sample #1

1

Input Sample #2

3 2 998244353

Output Sample #2

499122177

Input Sample #3

4 2 998244353

Output Sample #3

332748118

Input Sample #4

10 2 998244353

Output Sample #4

113919852

Input Sample #5

50 233 998244353

Output Sample #5

634280054

Notes

Sample Explanation

In the first set of data, the tree that can be generated is unique, so the two generated trees must be the same.

In the second set of data, there are only two trees that can be generated, and they are not isomorphic. Therefore, the probability that the two generated trees are isomorphic is $\frac{1}{2}$, which modulo 998244353 is 499122177.

In the third set of data, there are 6 trees that can be generated, as shown in the figure below. The second, third, and fourth trees (the middle three in the first row) are isomorphic, and the others are pairwise non-isomorphic. Therefore, the probability that the two generated trees are isomorphic is $\frac{1}{3}$, which modulo 998244353 is 332748118.

Data Range

For 100% of the data, it is guaranteed that $p$ is a prime number and $10^8 \le p \le 10^9$.

Thanks to @Xeonacid for providing the problem statement.

见题面 Input 部分

见题面 Output 部分