Description

Please note the special constraints on $\bm{n,k}$ in this problem.

$n$ players participated in $k$ Tetris Tournaments. Each Tetris Tournament consists of $n-1$ rounds. In each round, two currently uneliminated players $x$ and $y$ are selected to compete, and the loser is eliminated. The last remaining player is the winner. You are given that the $j$-th player was eliminated by $a_{i,j}$ in the $i$-th Tetris Tournament. Here, $j$ is the winner of the $i$-th tournament if and only if $a_{i,j} = 0$.

The players enjoy comparison. They all hope to surpass others in some way or at least be on a similar level.

Define that in the $i$-th Tetris Tournament, $x$ strictly dominates $y$ if and only if there exists a sequence $x = p_1, p_2, \dots, p_m = y$ (where $m \ge 2$, i.e., $x \neq y$) such that for all $1 \leq j < m$, $a_{i,p_{j+1}} = p_j$.

An ordered $k$-tuple of players $(i_1, i_2, \dots, i_k)$ is called level-similar if and only if for all $1 \leq j < k$, $i_j$ strictly dominates $i_{j+1}$ in the $j$-th tournament, and $i_k$ strictly dominates $i_1$ in the $k$-th tournament.

Your task is to compute the number of level-similar $k$-tuples, modulo $998244353$.

Input Format

The first line contains two positive integers $n$ and $k$. It is guaranteed that $\bm{3 \leq k \leq 5}$.

The next $k$ lines each contain $n$ non-negative integers $a_{i,1}, \ldots, a_{i,n}$, representing the elimination data for the $i$-th tournament.

Output Format

Output a single non-negative integer: the number of level-similar $k$-tuples, modulo $998244353$.

3 3
0 1 2
3 0 2
3 1 0

2

6 5
0 1 1 2 3 4
3 3 0 6 6 1
2 4 1 0 1 1
3 0 2 6 6 2
5 3 6 1 0 4

18

Hint

Sample Explanation #1

The valid $3$-tuples $(i_1, i_2, i_3)$ are: $(1, 2, 3)$ and $(2, 3, 1)$.

Constraints

This problem uses bundling tests.

• Special Constraint A: For $1 \leq i \leq n$, $a_{1,i} = a_{2,i}$.
• Special Constraint B: For $1 \leq i \leq k$, there do not exist $1 \leq j_1 < j_2 \leq n$ such that $a_{i,j_1} = a_{i,j_2}$.

For all test cases:

• $1 \leq n \leq 2.5 \times 10^5$,
• $\bm{3 \leq k \leq 5}$,
• The $a$ array is consistent with the problem description, and:
  • If $k=3$, $n \leq 2.5 \times 10^5$.
  • If $k=4$, $n \leq 7.5 \times 10^4$.
  • If $k=5$, $n \leq 4 \times 10^4$.

Translation by DeepSeek V3.