You are given a permutation $P$ of $\{1, 2, \dots, N\}$.
That is, $P$ is an array of length $N$ containing every integer from $1$ to $N$ exactly once.
You can perform the following operation on it:
- Choose an index $i$ ($1 < i < |P|$).
- Set $P_i = \max(P_{i-1}, P_i, P_{i+1})$.
- Delete $P_{i-1}$ and $P_{i+1}$ from $P$. The remaining elements are then re-indexed to start from $1$.
Each such operation reduces the length of $P$ by $2$. In particular, if the length of $P$ is $1$ or $2$, then this operation cannot be applied.
Find the number of distinct arrays that can be reached by performing this operation zero or more times starting from $P$.
Since this value might be large, you only need to find it modulo $998\,244\,353$.
Input
The input is given in the following format:
T N P_1 P_2 ... P_N ...
Constraints
- All input values are integers.
- $1 \le T \le 10^5$
- $1 \le N \le 5000$
- $1 \le P_i \le N$
- $P_i \ne P_j$ for all $i \ne j$.
- It is guaranteed that the sum of $N^2$ over all test cases does not exceed $5000^2$.
Output
For each test case, output a single integer — the number of distinct arrays that can be reached by performing the operation zero or more times on $P$, modulo $998\,244\,353$.
Example
Input 1
5 2 2 1 3 2 1 3 5 3 1 4 5 2 10 1 2 3 4 5 6 7 8 9 10 15 5 7 6 12 2 13 10 1 11 4 3 9 14 15 8
Output 1
1 2 5 55 365
Note
Test case 1: No operations can be performed.
Test case 2: There are two possibilities:
- Perform no operations. The final array is $[2, 1, 3]$.
- Perform one operation with $i = 2$. The final array is $[3]$.
These are the only reachable arrays.