A16475 | 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$ 取模。