[ZJOI2018] 树

题目描述

九条可怜是一个热爱出题的女孩子。 虽然出题本身是一件非常有趣的事情,但是要把题目给出成正式比赛,就不是那么有趣了:造数据总是一件让人心力憔悴的事情。 在 ZJOI2018 Day 1 中,可怜出了一道和树相关的非常有趣的题,她打算采用一种常用的方式随机生成一棵 $n$ 个节点的有根树: - 节点 1 作为树的根。 - 对于 $i \in [2, n]$ ,独立地从 $[1, i)$ 中等概率随机选取一个节点作为 $i$ 的父亲。 可怜不是很想考虑这样随机出来的数据能不能卡掉暴力,毕竟乱搞也是 OI 比赛的一部分。 可怜比较在意的是题目的区分度,以及是不是所有可能的分数都出现了。因此,可怜希望任何两个测试点的树是有区别的:这样就可能会有错误的程序能只通过其中一个点。 因此,可怜想要计算,通过上面的方法独立的随机生成 $k$ 棵 $n$ 个节点的有根树 $T_1$ 至 $T_k$ ,他们两两同构的概率是多少。 两棵 $n$ 个节点的有根树 $T_1$ 和 $T_2$ 同构当且仅当存在长度为 $n$ 的排列 $p$,满足 $p_1 = 1$ ,且对于 $\forall i \in [2, n]$ ,若 $i$ 在 $T_1$ 的父亲是 $f$ ,则 $p_i$ 在 $T_2$ 的父亲是 $p_f$ 。

输入输出格式

输入格式


第一行输入三个整数 $n, k, p$,表示节点个数,树的个数以及模数。输入保证 $10^8 \leq p \leq 10^9$ 且 $p$ 是质数。

输出格式


输出一行一个整数,表示答案对 $p$ 取模后的值。即如果答案的最简分数表示为 $\frac{a}{b}$ ,输出 $a \times b ^{-1} \bmod p$。

输入输出样例

输入样例 #1

2 2 998244353

输出样例 #1

1

输入样例 #2

3 2 998244353

输出样例 #2

499122177

输入样例 #3

4 2 998244353

输出样例 #3

332748118

输入样例 #4

10 2 998244353

输出样例 #4

113919852

输入样例 #5

50 233 998244353

输出样例 #5

634280054

说明

### 样例解释 在第一组数据中,能够生成的树是唯一的,因此生成的两棵树必定相同。 在第二组数据中,能够生成的树只有两种,他们是不同构的。因此生成的两棵树同构的概率为 $\frac{1}{2}$ ,在模 998244353 意义下为 499122177。 在第三组数据中,能够生成的树有 6 种,如下图所示。其中第二、三、四棵(第一排中间三棵)是同构的,其余两两不同构。因此生成的两棵树同构的概率为 $\frac{1}{3}$ ,在模998244353 意义下为 332748118。 ![](https://cdn.luogu.com.cn/upload/pic/18417.png) ### 数据范围 测试点| $n$| $k$|测试点| $n$| $k$ -|-|-|-|-|- 1|$\le 5$|$=2$|6|$\le 50$|$\le 10^9$ 2|$\le 10$|$=2$|7|$\le 200$|$\le 10^9$ 3|$\le 20$|$=2$|8|$\le 500$|$\le 10^9$ 4|$\le 50$|$=2$|9|$\le 1000$|$\le 10^9$ 5|$\le 50$|$=2$|10|$\le 2000$|$\le 10^9$ 对于 100% 的数据,保证 $p$ 是质数且 $10^8 \le p \le 10^9 $。 感谢 @Xeonacid 提供题面