P9493 "SFCOI-3" Arrange a Column

 (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.)

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 a**positive 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$.

**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 $T$ lines. Each line contains one integer, the answer.

### 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