Read problems statements in Mandarin chinese, Russian and Vietnamese as well.

Gritukan likes to take cyclic trips around the world. There are $N$ countries numbered $1$ through $N$ in the world. Before starting his travels, Gritukan chooses a permutation $P$ of all $N$ countries. Then, he visits all countries (some countries may be visited multiple times) using the following algorithm:
for each $v$ from $1$ to $N$ inclusive:
- travel to country $v$
- travel from country $v$ to country $P_{v}$, then from country $P_{v}$ to country $P_{P_{v}}$, and so on until he reaches country $v$ again; let's call this sequence of visited countries a cyclic route

(Each country appears at most once in a cyclic route. It is also possible for a route to contain only one country if $v=P_{v}$, in which case Gritukan's travel along this route consists of staying in country $v$.)

Unfortunately, Gritukan does not remember the routes he took. He only remembers a sequence $A_{1..N}$ with the following meaning: for each country $v$, the number of cyclic routes which contained this country is $A_{v}$. Given the sequence $A$, Gritukan asks you to calculate the number of permutations $P$ consistent with this sequence, modulo $998244353$ (it's prime).

------ Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains a single integer $N$.
The second line contains $N$ space-separated integers $A_{1}, A_{2}, \dots, A_{N}$.

------ Output ------
For each test case, print a single line containing one integer — the number of possible permutations modulo $998244353$ (it's prime).

------ Constraints ------
$1 ≤ T ≤ 100$
$1 ≤ N ≤ 10^{6}$
$1 ≤ A_{i} ≤ N$ for each valid $i$
the sum of $N$ over all test cases does not exceed $10^{6}$

------ Subtasks ------
Subtask #1 (40 points): $1 ≤ N ≤ 5000$

Subtask #2 (60 points): original constraints

----- Sample Input 1 ------
2
6
1 1 1 1 1 1
6
6 6 6 6 6 6
----- Sample Output 1 ------
1
120

见题面

见题面