CF2187F2.Al Fine (Counting Version)

This is the counting version of the problem. The difference between the versions is that in this version, you need to find the number of different common trees. Also, the constraint on $n$ in this version is smaller. You can hack only if you solved all versions of this problem.

For Christmas, Tortinita and Arietta each get a Christmas tree. Coincidentally, their trees share the same properties: both have $n+1$ vertices and are rooted at vertex $0$. In their Christmas card to you, each of them appends a DFS order sequence of their tree after their greetings. Recall that a DFS order sequence is generated by the following pseudocode.

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)

Let the DFS order sequence of Tortinita's tree be $a_0, a_1, \ldots, a_n$ and that of Arietta's tree be $b_0, b_1, \ldots, b_n$. You observe that $a_0 = b_0 = 0$, and since they are twin sisters, you wonder if they could have the exact same tree. Therefore, you want to find the number of different common trees$^{\text{∗}}$ for both sequences. Since the answer may be very large, you need to output it modulo $998\,244\,353$.

$^{\text{∗}}$Two trees are considered different if there exists a vertex label for which the set of its children's labels is not identical in both trees. In other words, the ordering of children for any given vertex does not matter.

这是该问题的计数版本。两个版本的区别在于：在本版本中，你需要求出不同的公共树的数量。此外，本版本中对 $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$；又因她们是双胞胎姐妹，你不禁好奇：她们是否可能拥有完全相同的树？因此，你想要求出对这两个序列而言，不同的公共树$^{\text{∗}}$ 的数量。由于答案可能非常大，你需要将结果对 $998\,244\,353$ 取模后输出。

$^{\text{∗}}$若存在某个顶点标签，使得该顶点在两棵树中的子节点标签集合不完全相同，则认为这两棵树不同。换言之，对于任意给定顶点，其子节点的顺序无关紧要。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains one integer $n$ ($2 \le n \le \boldsymbol{5000}$).

The second line of each test case contains $n$ integers $a_1, a_2, \cdots, a_n$ ($1 \le a_i \le n$).

The third line of each test case contains $n$ integers $b_1, b_2, \cdots, b_n$ ($1 \le b_i \le n$).

It is guaranteed that neither sequence $a$ nor $b$ contains duplicates.

It is guaranteed that the sum of $n^2$ over all test cases does not exceed $2.5\cdot10^7$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $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\cdot10^7$。

For each test case, output one integer — the number of different common trees modulo $998\,244\,353$.

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

In the first test case, the two different trees are tree A and tree B in the figure below. Note that tree B and tree C are the same.

In the second test case, the only common tree is tree B.

在第一个测试用例中，两棵不同的树是下图中的树 A 和树 B。注意，树 B 和树 C 是相同的。

在第二个测试用例中，唯一的公共树是树 B。