#SL2310C. Many Topological Problems
Many Topological Problems
许多拓扑问题
中文题目为机翻,原题目请参考英文题面
有一次你创建了下面的问题
拓扑问题
给你一棵有 顶点和一个整数 的带标签有根树。如果 ,并且 且每个 都有一个父序列 ,我们称长度为 的排列组合 为好排列组合。
求好的排列数。
现在,您觉得这个问题太简单了,于是又提出了下面的问题:
许多拓扑问题
给你两个整数 。对于顶点为 的所有不同标签的有根树 ,求 的 拓扑问题 答案之和,模数为 。
请解决多拓扑问题。
当且仅当两棵树的根不同,或者一条边存在于一棵树中而不存在于另一棵树中时,这两棵有标注根的树被认为是不同的。
输入
第一行包含一个整数 ,表示测试用例的数量。
对于每个测试用例,唯一一行包含两个整数 .
输出
对于每个测试用例,输出一行,用一个整数表示答案。
示例
3
2 2
5 1
114514 1919
2
120
354463397