由于评测机性能差异，本题时限额外增加了 3.5 秒。
一方通行在执行任务时接入了由御坂 号共 位御坂妹妹组成的临时御坂网络，每位御坂妹妹拥有一些信息，为了保证存储效率，妹妹们所拥有的信息互不相同。
临时御坂网络有两种连接 ，分别构成树形结构。
由于计算需求，妹妹们有时需要交换信息。具体地，若两位御坂妹妹间同时有两种连接，那么她们可以交换她们拥有的信息（不会保留自己原有的信息），同时会交换在 中的连接（即若另一位御坂妹妹和第一位有第二种连接，那么这个连接会变成她和第二位的，反之同理）。
最后之作非常好奇妹妹们拥有信息的不同状态有多少种，两种状态不同当且仅当存在一位御坂妹妹在这两种情况中所拥有的信息不同。
她设想了若干种网络的形态，并想对于每种形态都计算出上述问题的答案（因为是设想，所以并不一定保证 ）。
御坂网络在 1s 内就计算出了答案，不过因为好玩，所以最后之作想让你帮忙验算一下，你需要告诉她状态数对 取模的结果。
简要题意：
给定两棵 个点的无根树 ，节点编号为 。
有一个 的排列 ，初始时 ，你可以进行若干次操作，每次操作选择两个点 ，满足 在 中相邻且 在 中相邻，然后交换 和 ，问能得到多少种不同的 ，答案对 取模。
组数据。
