First, we transform the \(M\) permutations appropriately so that \(P^1=(1,2,\ldots,N)\). Let \(\mathrm{inv}\) be the inverse permutation of \(P^1\). Simultaneously replacing \(P^i_j\to P^i_{\mathrm{inv}_j}\) does not change the answer. From now on, we assume \(P^1=(1,2,\ldots,N)\).

Also, since \(P^i\) being a good permutation is equivalent to \(((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)\) being a good permutation, we set \(P^i_1=1\).

Hereafter, we consider trees as rooted trees with vertex \(1\) as the root. We call rooted trees for which \(P^1,P^2,\ldots,P^M\) are all good permutations wonderful rooted trees.

For a permutation \(Q\) with \(Q_1=1\), \(Q\) being a good permutation for rooted tree \(T\) is equivalent to the following:

• For any subtree of \(T\), if we let \(V\) be the vertex set contained in that subtree, then \(V\) can be appropriately arranged to form a contiguous subsequence of the inverse permutation of \(Q\).

Since we now have \(P^1=(1,2,\ldots,N)\), the vertex set of any subtree of a wonderful rooted tree can be expressed as \(\lbrace l,l+1,\ldots,r\rbrace\). For each \(l,r\), the question “Can \(\lbrace l,l+1,\ldots,r\rbrace\) be the vertex set of a subtree of a wonderful rooted tree?” can be computed in \(O(N^2M)\) time overall.

Finally, we can find the answer by doing DP with \(\mathrm{dp}[l][r]\) representing “the number of ways for subtrees with vertex set \(\lbrace l,l+1,\ldots,r\rbrace\)”. Since we need to decide the root within the subtree, the DP follows transitions like:

• \(\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])\)
  • Where vertex \(root\) is the root of the subtree, and the other vertices are decomposed into subtrees with vertex sets \(\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\)

This can be optimized using interval DP and computed in \(O(N^3)\) time.

mod = 998244353

N, M = map(int, input().split())
ok = [[1] * (N + 1) for _ in range(N)]  # Whether interval [l, r) can be the vertex set of a subtree of a wonderful rooted tree
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)]  # Number of ways interval [l, r) forms a rooted tree
dp2 = [[int(i == j) for j in range(N + 1)] for i in range(N + 1)]  # Number of ways interval [l, r) forms a rooted forest
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])