CF2187F2 Al Fine (Counting Version)

这是该问题的计数版本。与其他版本的不同之处在于，本版本需要你计算不同的公共树的数量。同时，本版本中 $n$ 的范围较小。只有在你解决了该问题的所有版本后，才能进行 hack。 在圣诞节，Tortinita 和 Arietta 各自收到了一棵圣诞树。巧合的是，她们的圣诞树都具有相同的性质：都有 $n+1$ 个结点，并且以 $0$ 号结点为根。在给你的圣诞贺卡中，她们分别将各自树的 DFS 序列添加在祝词后。回忆一下，DFS 序列的生成方式如下伪代码所示： ``` dfs_order = [] def dfs(v): dfs_order.append(v) pick an arbitrary permutation s of children of v for child in s: dfs(child) dfs(root) ``` 设 Tortinita 的树的 DFS 序列为 $a_0, a_1, \ldots, a_n$，Arietta 的树的 DFS 序列为 $b_0, b_1, \ldots, b_n$。你注意到 $a_0 = b_0 = 0$，由于她们是双胞胎姐妹，你好奇她们是否可能拥有完全相同的树。因此，你想找到两种序列下所有“公共树” $^{\ast}$ 的不同个数。由于答案可能非常大，你需要输出它对 $998\,244\,353$ 取模的结果。 $^{\ast}$ 若存在某个结点，其子结点编号的集合在两棵树中不同，则认为这两棵树是不同的。换句话说，对于任意结点，子结点的顺序无关紧要，只有其子结点的集合一致才认为是一棵相同的树。

每个测试点包含多组测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。 每个测试用例的第一行包含一个整数 $n$（$2 \le n \le \boldsymbol{5000}$）。 第二行为 $n$ 个整数 $a_1, a_2, \cdots, a_n$（$1 \le a_i \le n$）。 第三行为 $n$ 个整数 $b_1, b_2, \cdots, b_n$（$1 \le b_i \le n$）。 保证序列 $a$ 和 $b$ 均无重复元素。 保证所有测试用例中 $n^2$ 的和不超过 $2.5 \cdot 10^7$。

对于每个测试用例，输出一个整数，表示不同“公共树”的数量，对 $998\,244\,353$ 取模。

在第一个测试用例中，两棵不同的树分别为图中的树 A 和树 B。注意，树 B 和树 C 是相同的树。 在第二个测试用例中，唯一的公共树为图中的树 B。  由 ChatGPT 5 翻译