Counting Permutations with Consecutive Intervals

Consider a permutation \(P = [P_1, P_2, \dots, P_n]\) of the set \(\{1,2,\dots,n\}\). For any contiguous segment \(P_j, P_{j+1}, \dots, P_i\) (with \(1 \le j \le i \le n\)), define the segment to be continuous if and only if

[ \max{P_j, P_{j+1}, \dots, P_i} - \min{P_j, P_{j+1}, \dots, P_i} \le (i - j), ]

Note that for any segment of length \(m = i-j+1\), since the elements are distinct the minimum difference \(\max - \min\) is \(m-1\), so the above condition is equivalent to the requirement that the segment forms a set of consecutive integers (in any order).

For each permutation \(P\), define \(L_i\) (for \(1 \le i \le n\)) as the length of the longest continuous segment among all segments that end at position \(i\); that is,

[ L_i = \max{m \mid \text{there exists } j \text{ with } i-m+1 = j \text{ and } [P_j, P_{j+1}, \dots, P_i] \text{ is continuous}}, ]

with the convention that every segment of length 1 is continuous so (L_i \ge 1) for all (i). Furthermore, if a continuous interval is properly contained in another continuous interval with the same right endpoint, only the longest one is recorded.

You are given \(T\) test cases. For each test case, you are given an integer \(n\) and a sequence of \(n\) integers \(L_1, L_2, \dots, L_n\). Your task is to count the number of permutations \(P\) of \(\{1,2,\dots,n\}\) such that for every \(1 \le i \le n\), the longest continuous segment ending at \(i\) (in the sense defined above) has length exactly \(L_i\).

Since the answer can be large, output it modulo \(998244353\). Note that it is possible that no permutation satisfies the given information.

inputFormat

The first line contains a single integer \(T\) \( (1 \le T \le 50)\), the number of test cases. Then for each test case:

• The first line contains an integer \(n\) \( (1 \le n \le 8)\) -- the length of the permutation.
• The second line contains \(n\) space‐separated integers \(L_1, L_2, \dots, L_n\) \( (1 \le L_i \le n)\).

It is guaranteed that the total sum of \(n\) over all test cases does not exceed 50.

outputFormat

For each test case, output a single line containing one integer -- the number of permutations satisfying the given \(L\) information, taken modulo \(998244353\).

sample

2
2
1 2
3
1 1 3

2
2