Migrated from Lutece 3222 随机的树

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Tag: Symbolic Method

考虑这样一种随机生成 $n$ 个点的有根树的方式：

• 以 $1$ 为根，对于 $i\in [2,n]$，在 $[1,i)$ 中均匀随机一个点作为 $i$ 的父亲。

只生成一棵树太简单了，现在问按此方式随机生成 $k$ 颗 $n$ 个点的有根树，他们两两同构的概率是多少，对 $p$ 取模。

两棵 $n$ 个点的有根树 $T_1,T_2$ 同构当且仅当存在一个长为 $n$ 的排列 $p$，满足 $p_1=1$，且 $\forall i \in [2,n]$，$i$ 在 $T_1$ 中的父亲是 $f$，则在 $T_2$ 中 $p_i$ 的父亲是 $p_f$。

Input

第一行三个正整数 $n,k,p$，表示点数，树的个数和模数。

Output

一行一个正整数表示答案。

Samples

2 2 998244353

1

3 2 998244353

499122177

4 2 998244353

332748118

10 2 998244353

113919852

50 233 998244353

634280054

Constraints

$2\le n\le 2000$

$2\le k\le 10^9$

$10^8\le p\le 10^9$ 且 $p$ 是质数。

Resources

2024 UESTC ICPC Training for Math