题目描述

请注意本题对 $\bm{n,k}$ 的特殊限制。

$n$ 名选手参加了 $k$ 场 Tetris Tournament。每一场 Tetris Tournament 包含 $n-1$ 轮，每轮会选出两个目前还未淘汰的选手 $x,y$ 并让他们参加一场比赛，输的人淘汰。最后会有唯一胜者。你现在得知第 $j$ 个人在第 $i$ 场 Tetris Tournament 中被 $a_{i,j}$ 淘汰了。$j$ 是第 $i$ 场 Tetris Tournament 的胜者当且仅当 $a_{i,j}=0$。

选手们喜欢比较。他们都希望自己在某种意义上能够胜过别人，或至少跟别人水平差不多。

定义第 $i$ 场 Tetris Tournament 中 $x$ 严格吊打 $y$ 当且仅当存在 $x=p_1,p_2,\dots,p_m=y$（$m\ge 2$，也就是说 $x\neq y$），使得对于任意 $1\leq j<m$，$a_{i,p_{j+1}}=p_j$。

定义一个有序的选手 $k$ 元组 $(i_1,i_2,\dots,i_k)$ 是水平相似的当且仅当对于 $1\leq j<k$，$i_j$ 在第 $j$ 场比赛中严格吊打 $i_{j+1}$ 且 $i_k$ 在第 $k$ 场比赛中严格吊打 $i_1$。

求水平相似的 $k$ 元组数量，对 $998244353$ 取模。

输入格式

第一行，两个正整数 $n,k$。保证 $\bm{3\leq k\leq 5}$。

接下来 $k$ 行，第 $i$ 行 $n$ 个非负整数 $a_{i,1}, \ldots, a_{i,n}$。

输出格式

仅一行，一个非负整数，表示水平相似的 $k$ 元组数量，对 $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

提示

【样例解释 #1】

符合要求的三元组 $(i_1,i_2,i_3)$ 有：$(1,2,3)$，$(2,3,1)$。

【数据范围】

本题使用捆绑测试。

• 特殊性质 A：对于 $1\leq i\leq n$，$a_{1,i}=a_{2,i}$；
• 特殊性质 B：对于 $1\leq i\leq k$，不存在 $1\leq j_1<j_2\leq n$ 使得 $a_{i,j_1}=a_{i,j_2}$。

对于所有数据：$1\leq n\leq2.5\times10^5$，$\bm{3\leq k\leq 5}$，保证 $a$ 数组符合题意，且：

• $k=3$ 时，$n\leq2.5\times10^5$；
• $k=4$ 时：$n\leq7.5\times10^4$；
• $k=5$ 时：$n\leq4\times10^4$。