"Perhaps my life is already like a candle in the wind," Xiao Lv said.
Xiao Lv has developed a keen interest in the concept of "continuity" due to his calculus course. He intends to apply the concept of continuity to sequences of integers. He defines an integer sequence of length $m$ as continuous if and only if the difference between the maximum and minimum values in the sequence does not exceed $m - 1$. For example, $\{1, 3, 2\}$ is continuous, while $\{1, 3\}$ is not.
One day, Xiao Lv's boss, Ban Laoda, gave him $T$ permutations of length $n$. Xiao Lv was delighted and determined whether each interval of each permutation was "continuous" according to his definition. However, Xiao Lv felt that "continuous" intervals contained within other "continuous" intervals were not significant enough. Therefore, for each permutation, he only recorded the length of the longest "continuous" interval ending at each position. That is, for every permutation given by Ban Laoda, he recorded the length $L_i$ of the longest "continuous" interval ending at $i$ for every $1 \le i \le n$. Obviously, this length is at least 1, as all integer sequences of length 1 are continuous.
After finishing all this, Xiao Lv climbed into his green bed and had a beautiful green dream.
However, when he woke up the next day, Xiao Lv was surprised to find that all the permutations given by Ban Laoda were gone, and only the $T$ sets of information he recorded remained. Xiao Lv knew he was in trouble, but as a curious young man, he still wanted to know: for each set of information, how many permutations of length $n$ are consistent with it?
Since Xiao Lv has already given up, you only need to tell him the result of each answer modulo 998244353.
We do not guarantee that there exists at least one permutation consistent with the information, as Xiao Lv is human and he might have made mistakes.
Input
The first line contains two integers $T$ and $n$, representing the number of permutations and the length of each permutation, respectively.
The next $T$ lines each describe a set of information, containing $n$ positive integers. The $j$-th integer $L_{i, j}$ in the $i$-th set of information represents the length of the longest "continuous" interval ending at the $j$-th position in the $i$-th permutation.
For each line, if it contains multiple numbers, they are separated by single spaces.
Output
For each set of information, output one integer per line representing the number of possible permutations, modulo 998244353.
Examples
Input 1
1 3 1 1 3
Output 1
2
Examples 2
See green/green2.in and green/green2.ans in the contestant directory.
Examples 3
See green/green3.in and green/green3.ans in the contestant directory.
Subtasks
| Test Case ID | $n \le$ | $T \le$ | Special Properties |
|---|---|---|---|
| 1 ~ 2 | 10 | 1 | None |
| 3 ~ 4 | 10 | 100 | None |
| 5 | 300 | 1 | $L_{i, j} = j$ |
| 6 | 300 | 1 | $L_{i, j} = 1$ and $j < n$ |
| 7 ~ 8 | 100 | 100 | None |
| 9 | 1000 | 1 | $L_{i, j} = 1$ and $j < n$ |
| 10 ~ 12 | 1000 | 100 | None |
| 13 ~ 16 | 5000 | 100 | None |
| 17 ~ 20 | 50,000 | 100 | None |
For all test data, $1 \le T \le 100$, $1 \le N \le 50000$, $1 \le L_{i, j} \le j$.
Note
The input size for some test cases in this problem is large; please pay attention to input efficiency.