L. Label the Tree
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a rooted tree$$$^{\text{∗}}$$$ with $$$n$$$ vertices numbered from $$$1$$$ to $$$n$$$. The root is the vertex $$$1$$$.

A permutation$$$^{\text{†}}$$$ $$$p_1,p_2,\dots,p_n$$$ is good if and only if, for each $$$1 \le i \le n$$$, at least one of the following conditions is true:

  • $$$p_i = i$$$.
  • Vertex $$$p_i$$$ is an ancestor$$$^{\text{‡}}$$$ of vertex $$$i$$$.
  • Vertex $$$p_i$$$ is a descendant$$$^{\text{§}}$$$ of vertex $$$i$$$.

Count the number of good permutations of length $$$n$$$, modulo $$$998\,244\,353$$$.

$$$^{\text{∗}}$$$A tree is a connected graph without cycles. A rooted tree is a tree where one vertex is special and called the root.

$$$^{\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).

$$$^{\text{‡}}$$$An ancestor of vertex $$$v$$$ is any vertex on the simple path from $$$v$$$ to the root, including the root, but not including $$$v$$$. The root has no ancestors.

$$$^{\text{§}}$$$A descendant of vertex $$$v$$$ is any vertex $$$u$$$ for which $$$v$$$ is an ancestor. No vertex is its own descendant.

Input

The first line contains $$$t$$$ ($$$1 \le t \le 2\,500$$$) — the number of test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 5\,000$$$) — the number of vertices.

The second line contains $$$n - 1$$$ integers $$$a_2, a_3, \ldots, a_n$$$ ($$$1 \le a_i \le i-1$$$) — $$$a_i$$$ represents the parent of the vertex $$$i$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$5\,000$$$.

Output

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

Example
Input
5
3
 
3
 
6
    
7
     
13
Output
3
6
20
75
237554682
Note

In the first test case, the good permutations are $$$[1,2,3]$$$,$$$[2,1,3]$$$, and $$$[3,2,1]$$$.

In the second test case, all $$$3!=6$$$ permutations are good.