まず，\(P^1=(1,2,\ldots,N)\) となるように \(M\) 個の順列を適宜変換します．\(P^1\) の逆順列を \(\mathrm{inv}\) として，\(P^i_j\to P^i_{\mathrm{inv}_j}\) と同時に置き換えても答えは変わりません．以降では \(P^1=(1,2,\ldots,N)\) とします．

また，\(P^i\) が良い順列であることと \(((P^i_1+k\ \mathrm{mod} \ N) + 1,(P^i_2+k\ \mathrm{mod} \ N) + 1,\ldots,(P^i_N+k\ \mathrm{mod} \ N) + 1)\) が良い順列であることは同値なので，\(P^i_1=1\) とします．

以降，木は頂点 \(1\) を根とする根付き木とします．\(P^1,P^2,\ldots,P^M\) がすべて良い順列になるような根付き木を すばらしい根付き木 と呼ぶことにします．

\(Q_1=1\) である順列 \(Q\) が根付き木 \(T\) の良い順列であることは，以下と同値です．

• \(T\) の任意の部分木に対して，その部分木に含まれる頂点集合を \(V\) としたとき，\(V\) をうまく並べることで \(Q\) の逆順列の連続部分列にすることができる．

いま \(P^1=(1,2,\ldots,N)\) としていることから，すばらしい根付き木の任意の部分木の頂点集合は \(\lbrace l,l+1,\ldots,r\rbrace\) とあらわせます．各 \(l,r\) について，「\(\lbrace l,l+1,\ldots,r\rbrace\) はすばらしい根付き木の部分木の頂点集合にできるか？」という問題は，全体で \(O(N^2M)\) で計算できます．

あとは，\(\mathrm{dp}[l][r]\) を「\(\lbrace l,l+1,\ldots,r\rbrace\) を頂点集合とする部分木の場合の数」として dp をすることで答えを求めることができます．部分木の中の根を決める必要があるため，dp は

• \(\mathrm{dp}[l][r]\leftarrow (\mathrm{dp}[l][i_1-1]\times \mathrm{dp}[i_1][i_2-1]\times \dots \times\mathrm{dp}[i_{\ast}][root-1])\times (\mathrm{dp}[root+1][j_1-1]\times \mathrm{dp}[j_1][j_2-1]\times \dots \times\mathrm{dp}[j_{\ast}][r])\)
  • 頂点 \(root\) を部分木の根とし，\(root\) 以外の頂点は \(\lbrace l,i_1-1\rbrace,\lbrace i_1,i_2-1\rbrace,\ldots,\lbrace i_\ast,root-1\rbrace,\lbrace root+1,j_1-1\rbrace,\lbrace j_1,j_2-1\rbrace,\ldots,\lbrace j_\ast,r\rbrace\) という頂点集合からなる部分木に分解される場合

のような遷移をたどります．これは区間 dp で高速化することができて \(O(N^3)\) で計算できます．

mod = 998244353

N, M = map(int, input().split())
ok = [[1] * (N + 1) for _ in range(N)]  # 区間 [l, r) をすばらしい根付き木の部分木の頂点集合としてよいか
for i in range(M):
    P = list(map(lambda x: int(x) - 1, input().split()))
    if i == 0:
        inv = [0] * N
        for j, p in enumerate(P):
            inv[p] = j
    Q = [(P[inv[j]] - P[inv[0]]) % N for j in range(N)]
    pos = Q[Q.index(0) :] + Q[: Q.index(0)]
    for l in range(N):
        mn, mx = N, -1
        for r in range(l, N):
            mn = min(mn, pos[r])
            mx = max(mx, pos[r])
            ok[l][r + 1] &= r - l == mx - mn

dp1 = [[0] * (N + 1) for i in range(N + 1)]  # 区間 [l, r) が根付き木をなすもの
dp2 = [[int(i == j) for j in range(N + 1)] for i in range(N + 1)]  # 区間 [l, r) が根付き森をなすもの
for r in range(N + 1):
    for l in range(r - 1, 0, -1):
        if ok[l][r]:
            for m in range(l, r):
                dp1[l][r] = (dp1[l][r] + dp2[l][m] * dp2[m + 1][r]) % mod
        for m in range(l, r):
            dp2[l][r] = (dp2[l][r] + dp2[l][m] * dp1[m][r]) % mod
            
print(dp2[1][N])