CF2164F1 Chain Prefix Rank (Easy Version)

**This is the easy version of the problem. The difference between the versions is that in this version, $n \le 5000$. You can hack only if you solved all versions of this problem.** Given a tree $T$ with $n$ vertices rooted at $1$ and a sequence $a$ of length $n$, count the number of permutations$^{\text{∗}}$ $p$ of length $n$ that satisfy the following condition: - For all $1 \le u \le n$, there are exactly $a_u$ vertices $v$ such that $v$ is an ancestor of $u$ in $T$ and $p_v < p_u$. Output the answer modulo $998\,244\,353$. Input data is selected in such a way that at least one valid permutation exists. $^{\text{∗}}$A permutation of length $n$ is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ($2$ appears twice in the array), and $[1,3,4]$ is also not a permutation ($n=3$ but there is $4$ in the array).

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 2500$). The description of the test cases follows. The first line of each test case contains an integer $n$ ($2 \le n \le 5000$) — the number of vertices. The second line of each test case contains $n-1$ integers $fa_2,fa_3,\ldots,fa_n$ ($1 \le fa_i < i$)— $fa_i$ is the parent of $i$ on $T$. The third line of each test case contains $n$ integers $a_1,a_2,\ldots,a_n$ ($0 \le a_i < n$). It is guaranteed that the sum of $n$ over all test cases does not exceed $5000$. Input data is selected in such a way that at least one valid permutation exists.

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

[Visualizer link](https://codeforces.com/assets/contests/2164/F_ahVa9noocebeero5shie.html) In the first test case, the only permutation which satisfies the condition is $[1,2,3,4,5]$. In the second test case, permutations which satisfy the condition are $[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]$. In the third test case, permutations which satisfy the condition are $[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]$.