D. Counting Minimal Graphs
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Note: You may want to use $$$64$$$-bit integers instead of $$$32$$$-bit integers in this task. For example, in Java, you may want to use long instead of int. In C++, you may want to use long long.

Serval has an undirected unweighted connected graph of $$$n$$$ nodes and $$$m$$$ edges.

To help you guess the structure of the graph, Serval tells you the distance from node $$$1$$$ to node $$$i$$$ for each $$$2 \leq i \leq n$$$ (distance from node $$$1$$$ to node $$$i$$$ is the minimum number of edges in any path from $$$1$$$ to $$$i$$$). Additionally, Serval tells you that the number of edges in the graph is minimized. That is, there does not exist a graph that also satisfies the distance requirements with less edges.

Despite this, there can still be a lot of possible graphs! Please count the number of graphs with minimum number of edges that satisfies the distance requirements. Since the answer can be massive, output it modulo $$$998\,244\,353$$$.

Input

The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) – the number of independent test cases. Descriptions of the test cases follow.

The first line of each test case contains an integer $$$n$$$ ($$$2 \leq n \leq 2\cdot 10^5$$$) – the number of nodes in the graph.

The following line contains $$$n-1$$$ integers $$$d_2,d_3,\ldots,d_n$$$ ($$$1 \leq d_i \leq n-1$$$) – the distances from node $$$1$$$ to each other node.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2\cdot 10^5$$$.

Output

For each test case, output the number of graphs modulo $$$998\,244\,353$$$.

Example
Input
5
2
1
4
1 2 1
9
1 2 1 3 4 3 2 2
8
1 2 3 4 5 6 7
4
1 3 3
Output
1
2
144
1
0
Note

In the second test case, the two graphs are shown below

Note that we cannot have both edges 2 3 and 4 3 as the graph would have $$$4$$$ edges, while the minimal graph has $$$3$$$ edges.

In the last test case, no graph exists.