Description

Because of a calculus course, Xiao Lü has become very interested in the concept of "continuity". He plans to bring the concept of continuity to sequences of integers. He defines an integer sequence of length $m$ to be continuous if and only if the difference between the maximum and minimum elements in the sequence does not exceed $m-1$. For example, $\{1,3,2\}$ is continuous, while $\{1,3\}$ is not.

One day, Xiao Lü’s direct supervisor, Boss Ban, gave him $T$ permutations of length $n$. Delighted, Xiao Lü determined, for each permutation, whether each interval is "continuous" as he defined. However, he felt that "continuous" intervals contained within other "continuous" intervals were not good enough. Therefore, for all "continuous" intervals in each permutation with the same right endpoint, he recorded only the length of the longest such "continuous" interval. In other words, for each permutation given by Boss Ban, he recorded for each $1 \le i \le n$ the length $L_i$ of the longest "continuous" interval whose right endpoint is $i$. Clearly, this length is at least $1$, because all integer sequences of length $1$ are continuous.

After finishing all this, Xiao Lü climbed onto his green bed and had a lovely green dream.

But when he woke up the next day, he was shocked to find that all the permutations Boss Ban had given him were gone, leaving only the $T$ recorded sets of information. Knowing he was doomed, yet being a curious young man, he still wanted to know: for each set of information, how many length-$n$ permutations are consistent with it?

Since Xiao Lü has already given up on treatment, you only need to tell him each answer modulo $998244353$.

We do not guarantee that there exists at least one permutation consistent with the information, because Xiao Lü is human and can make mistakes.

Input Format

The first line contains two integers $T, n$, representing the number of permutations Boss Ban gave and the length of each permutation.

The next $T$ lines each describe one set of information and contain $n$ positive integers. In the $i$-th set, the $j$-th integer from left to right $L_{i,j}$ denotes, in the $i$-th permutation, the length of the longest "continuous" interval whose right endpoint is the $j$-th position.

Within each line, if there are multiple numbers, they are separated by a single space.

Output Format

For each set of information, output a single integer on its own line representing the number of possible permutations modulo $998244353$. Since the computer is doing the calculation, we will not give you a chance to make a mistake.

1 3
1 1 3

2

Hint

Constraints

For all testdata, $1 \le T \le 100, 1 \le n \le 50000, 1 \le L_{i,j} \le j$.
Some test points have large input size; please be mindful of input speed.

Translated by ChatGPT 5