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

Source: codechef | Difficulty: VERY_HARD
Tags: Matrices

Combinatorics

Number theory

Mathematics

Polynomials and generating functions


Solutions:
from itertools import permutations
from collections import defaultdict as df
from bisect import bisect_left as bl
import sys
mod = 998244353
F = [1] * (10 ** 6 + 10)
for i in range(1, 10 ** 6 + 10):
	F[i] = F[i - 1] * i % 998244353

def c(n, r):
	return F[n] * pow(F[r], mod - 2, mod) * pow(F[n - r], mod - 2, mod) % mod
for _ in range(int(input())):
	n = int(input())
	A = [int(x) for x in input().split()]
	C = df(int)
	for i in A:
		C[i] += 1
	ans = 1
	for i in C:
		if C[i] % i != 0:
			ans = 0
			break
		for j in range(C[i] // i):
			ans *= c(C[i] - 1, i - 1) * F[i - 1]
			ans %= mod
			C[i] -= i
	print(ans)