Background

(In fact, this problem was originally called I must say No, but for some obvious reasons the title was changed /kk.)

You must say Yes.

(The background image comes from Phigros artwork. If there is any infringement, please inform the problem setter.)

Problem Description

Little R has a permutation $p_1 \dots p_n$ of length $n$. In other words, $p_1 \dots p_n$ contains the numbers from $0$ to $(n - 1)$, and among these $n$ numbers, each number appears in $p$ exactly once.

Little R has $n$ constraints. The $i$-th constraint $(0 \le i \le n - 1)$ is described by apositive integer $L_i$, meaning that there exists at least one interval $[l, r]$ of length $L_i$ (i.e. $r - l + 1 = L_i$) such that $\operatorname{mex}_{k=l}^r p_k = i$.

Little R has lost the permutation $p_1 \dots p_n$, but fortunately she still remembers these $n$ constraints. Please help her find how many initial permutations are valid. Output the answer modulo $998244353$.

Input Format

This problem has multiple test cases in each test point.

The first line contains an integer $T$, the number of test cases. For each test case:

• The first line contains an integer $n$.
• The second line contains $n$ integers, representing $L_0 \dots L_{n-1}$ in order.

Output Format

Output $T$ lines. Each line contains one integer, the answer.

4
4
1 1 3 3
5
2 1 3 3 4
6
1 1 2 5 4 5
10
3 2 3 4 7 6 8 8 8 9

4
12
8
96

Hint

Definitions

• The $\operatorname{mex}$ of a sequence is the smallest non-negative integer that does not appear in it. For example, $\operatorname{mex}\{1, 3, 4\} = 0$, $\operatorname{mex}\{0, 1, 1, 2, 5\} = 3$, $\operatorname{mex}\{3, 1, 0, 2\} = 4$.

Constraints

• Subtask 0 (10 pts): $n \le 10$.
• Subtask 1 (30 pts): $n \le 18$.
• Subtask 2 (15 pts): $n \le 300$.
• Subtask 3 (45 pts): no special constraints.

For all testdata, $1 \le T \le 10$, $1 \le n \le 5 \times 10^3$, $1 \le L_i \le n$.

Translated by ChatGPT 5