Forgotten Map - Repovive Standard Round 8 | Repovive

26D. Forgotten Map

2000 pts2s256 MB

Dinosaurs lived in $n$ nests, numbered from $1$ to $n$ . The roads between the nests formed a tree.

Starting on night $1$ , consider the nests that have not yet been evacuated. Every such nest with roads directly connecting it to at most one other such nest is evacuated. These evacuations happen simultaneously, using the nests remaining at the start of the night.

The map has been lost. You are given an array $a_1, a_2, \ldots, a_n$ , where $a_i$ is the night on which nest $i$ was evacuated.

For each test case, compute $\mathrm{answer}$ , the number of different maps consistent with this information, modulo $998244353$ . If no consistent map exists, the answer is $0$ . Two maps are different if their sets of roads are different. A road is an undirected edge between two distinct nests.

Constraints

$1 \le t \le 10^4$
$1 \le n \le 2\times 10^5$
$1 \le a_i \le n$
The sum of $n$ over all test cases is at most $2 \times 10^5$ .

Input

t

\left. \begin{array}{l} n \\ a_1 \quad a_2 \quad \cdots \quad a_n \end{array} \right\} \times t

Output

\left. \begin{array}{l} \mathrm{answer} \end{array} \right\} \times t

Samples

Input

Case 1

1
1

Case 2

5
1 1 2 1 1

Explanation

Case 1

There is one nest and no roads. It is evacuated on night 1, so the empty road set is the only map.

Case 2

The only compatible map connects nest 3 directly to each of the other four nests. Nests 1, 2, 4, and 5 are evacuated on night 1, and nest 3 is evacuated on night 2.

Output

Case 1

Case 2

Input

Case 1

4
1 2 2 1

Case 2

3
1 2 2

Case 3

6
1 1 1 2 2 3

Explanation

Case 1

There are two compatible maps. Their road sets are {(1, 2), (2, 3), (3, 4)} and {(1, 3), (2, 3), (2, 4)}. In both maps, nests 1 and 4 are evacuated first, followed by nests 2 and 3.

Case 2

Every tree on three nests has two leaves. At least two nests must therefore be evacuated on night 1, while the given information lists only nest 1. No compatible map exists.

Case 3

There are 12 compatible maps. One of them has roads (1, 4), (2, 4), (3, 5), (4, 6), and (5, 6). It evacuates nests 1, 2, and 3 on night 1, nests 4 and 5 on night 2, and nest 6 on night 3.

Output

Case 1

Case 2

Case 3

Dinosaurs lived in $n$ nests, numbered from $1$ to $n$ . The roads between the nests formed a tree.

The map has been lost. You are given an array $a_1, a_2, \ldots, a_n$ , where $a_i$ is the night on which nest $i$ was evacuated.

$1 \le t \le 10^4$
$1 \le n \le 2\times 10^5$
$1 \le a_i \le n$
The sum of $n$ over all test cases is at most $2 \times 10^5$ .

t

\left. \begin{array}{l} n \\ a_1 \quad a_2 \quad \cdots \quad a_n \end{array} \right\} \times t

\left. \begin{array}{l} \mathrm{answer} \end{array} \right\} \times t

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

26D. Forgotten Map

Constraints

Input

Output

Samples

26D. Forgotten Map

Constraints

Input

Output

Samples