CFCF2164F1.Chain Prefix Rank (Easy Version)

这是该问题的简单版本。不同版本的区别在于本版本中 $n \leq 5000$。只有在你完成所有版本后才能进行 hack。

给定一棵有 $n$ 个结点、以 $1$ 为根的树 $T$ 以及一个长度为 $n$ 的序列 $a$，请计算满足下列条件的排列 $^{\text{∗}}$ $p$ 的个数：

• 对于所有 $1 \leq u \leq n$，恰好有 $a_u$ 个结点 $v$ 是 $u$ 在树 $T$ 中的祖先，并且 $p_v < p_u$。

请输出答案对 $998\,244\,353$ 取模的结果。保证输入数据至少存在一个合法排列。

$^{\text{∗}}$ 长度为 $n$ 的排列指由 $1$ 至 $n$ 的 $n$ 个不同整数任意排列组成的数组。例如，$[2,3,1,5,4]$ 是一个排列，但 $[1,2,2]$ 不是排列（$2$ 在数组中出现了两次），$[1,3,4]$ 也不是排列（$n=3$ 但数组中出现了 $4$）。

每组测试包含多个测试用例。第一行包含测试用例数 $t$（$1 \leq t \leq 2500$）。接下来是每个测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$2 \leq n \leq 5000$）——结点数。

每个测试用例的第二行包含 $n-1$ 个整数 $fa_2, fa_3, \ldots, fa_n$（$1 \leq fa_i < i$），表示 $i$ 在树 $T$ 中的父亲编号。

每个测试用例的第三行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$0 \leq a_i < n$）。

保证所有测试用例的 $n$ 之和不超过 $5000$。输入数据保证至少存在一个合法排列。

对于每个测试用例，输出一个整数，表示满足条件的排列数量，对 $998\,244\,353$ 取模。

可视化链接

在第一个样例中，唯一满足条件的排列是 $[1,2,3,4,5]$。

在第二个样例中，满足条件的排列有 $[4,5,1,2,3]$、$[4,5,1,3,2]$、$[4,5,2,1,3]$、$[4,5,2,3,1]$、$[4,5,3,1,2]$、$[4,5,3,2,1]$。

在第三个样例中，满足条件的排列有 $[3,1,6,2,5,7,8,4]$、$[3,1,6,2,5,8,7,4]$、$[3,2,6,1,5,7,8,4]$、$[3,2,6,1,5,8,7,4]$。