BZPRO

#5307. [Zjoi2018]树

内存限制：512 MiB 时间限制：30 Sec
提交 提交记录 讨论

题目描述

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

输入格式

第一行输入三个整数n,k,p，表示节点个数，树的个数以及模数。
10^8<=p<=10^9,且p是质数。
N<=2000
K<=10^9

输出格式

输出一行一个整数，表示答案对p取模后的值。
即如果答案的最简分数表示为a/b，输出a×b−1 mod p。

样例

样例输入


			
2 2 998244353

3 2 998244353

4 2 998244353

10 2 998244353

50 233 998244353

样例输出


			
1

499122177

332748118

113919852

634280054

样例中有五组不同的数据，所以输入格式略有不同。

在实际的测试数据中，输入只有一行。在第一组数据中，能够生成的树是唯一的，

因此生成的两棵树必定相同。

在第二组数据中，能够生成的树只有两种，他们是不同构的。

因此生成的两棵树同构的概率为1，在模998244353意义下为499122177。

在第三组数据中，能够生成的树有6种，如下图所示。

其中第二、三、四棵（第一排中间三棵）是同构的，其余两两不同构。

因此生成的两棵树同构的概率为1，在模998244353意义下为332748118。

数据范围与提示

BZPRO Powered by Remmina.
Github Repository