九条可怜是一个热爱出题的女孩子。
虽然出题本身是一件非常有趣的事情,但是要把题目给出成正式比赛,就不是那么有趣了:造数据总是一件让人心力憔悴的事情。
在 ZJOI2018 Day 1 中,可怜出了一道和树相关的非常有趣的题,她打算采用一种常用的方式随机生成一棵
• 节点
• 对于
可怜不是很想考虑这样随机出来的数据能不能卡掉暴力,毕竟乱搞也是 OI 比赛的一部分。
可怜比较在意的是题目的区分度,以及是不是所有可能的分数都出现了。因此,可怜希望任何两个测试点的树是有区别的:这样就可能会有错误的程序能只通过其中一个点。
因此,可怜想要计算,通过上面的方法独立的随机生成
两棵
输入格式
第一行输入三个整数
输出格式
输出一行一个整数,表示答案对
样例一
input
2 2 998244353 3 2 998244353 4 2 998244353 10 2 998244353 50 233 998244353
output
1 499122177 332748118 113919852 634280054
explanation
样例中有五组不同的数据,所以输入格式略有不同。在实际的测试数据中,输入只有一行。
在第一组数据中,能够生成的树是唯一的,因此生成的两棵树必定相同。
在第二组数据中,能够生成的树只有两种,他们是不同构的。因此生成的两棵树同构的概率为
在第三组数据中,能够生成的树有
限制与约定
测试点编号 | ||
---|---|---|
对于 100% 的数据,保证
时间限制: 3s
空间限制: 512MB