#P18185. Again Permutation Problem

Again Permutation Problem

Again Permutation Problem

给定 MM 个 1,2,…,N1,2,\ldots,N 的排列。第 ii 个排列记为 Pi=(Pi,1,Pi,2,…,Pi,N)P_i=(P_{i,1},P_{i,2},\ldots,P_{i,N})。

最初,序列 Q=(1,2,…,N)Q=(1,2,\ldots,N)。你可以执行任意次以下操作,也可以不执行:

  • 选择一个 1≤i≤M1\le i\le M,把 QQ 更新为 (QPi,1,QPi,2,…,QPi,N)(Q_{P_{i,1}},Q_{P_{i,2}},\ldots,Q_{P_{i,N}})。

考虑经过任意次操作后所有能够得到的不同序列 QQ。求这些序列的逆序数之和,对 998244353998244353 取模。

序列的逆序数是满足 1≤u<v≤N1\le u<v\le N 且 Qu>QvQ_u>Q_v 的下标对 (u,v)(u,v) 的个数。同一序列无论可以用多少种操作序列得到,都只统计一次。

输入格式

第一行两个整数 N,MN,M。

接下来 MM 行,每行 NN 个整数,第 ii 行表示排列 PiP_i。

输出格式

输出一个整数,表示所有可达不同序列的逆序数之和,模 998244353998244353。

数据范围

  • 1≤N,M≤301\le N,M\le30;
  • 每个 PiP_i 都是 1,2,…,N1,2,\ldots,N 的一个排列;
  • 不同的 PiP_i 可以相同,也可以是恒等排列;
  • 所有输入均为整数。

样例 1

输入

3 2
1 2 3
2 3 1

输出

4

样例 2

输入

5 2
3 4 5 1 2
1 5 4 3 2

输出

50

样例 3

输入

30 12
1 2 9 4 5 6 7 8 3 10 11 12 19 14 15 25 17 18 20 26 21 22 23 24 16 29 27 28 13 30
9 2 27 4 5 10 7 8 1 25 11 12 24 14 15 16 17 18 19 20 21 22 23 28 6 26 3 13 29 30
1 5 3 29 2 6 7 8 9 10 11 12 13 16 15 18 17 14 19 20 21 22 28 27 25 26 24 23 4 30
7 2 3 25 5 6 1 28 21 15 11 12 13 14 10 17 16 18 19 20 9 22 23 24 4 26 27 8 29 30
1 2 5 4 16 6 7 8 9 11 10 3 13 14 15 12 17 23 19 20 21 29 18 24 25 26 27 28 22 30
19 24 3 4 1 6 7 8 9 10 11 12 13 21 15 16 17 18 5 22 20 14 23 2 25 26 27 28 29 30
1 2 3 4 5 6 27 8 9 10 29 12 24 14 15 16 17 18 30 20 7 22 13 23 25 26 21 28 11 19
1 2 25 4 5 6 7 8 9 20 23 12 13 14 15 16 17 18 19 10 29 22 3 24 11 26 27 28 30 21
1 2 16 4 5 6 3 8 9 10 11 12 22 29 13 7 17 18 19 20 21 15 23 24 14 26 27 28 25 30
1 13 3 4 5 6 21 8 24 10 7 12 20 14 15 16 17 2 19 18 11 22 23 9 25 26 27 28 29 30
1 2 3 4 5 6 25 8 9 19 11 12 13 7 10 16 21 18 15 20 17 22 23 24 28 26 27 14 29 30
1 2 27 21 5 6 7 8 9 10 18 24 13 14 15 16 17 12 19 11 4 22 23 20 25 26 3 28 29 30

输出

701414999

样例 1 中恰有三个可达序列 (1,2,3)(1,2,3)、(2,3,1)(2,3,1)、(3,1,2)(3,1,2),逆序数分别为 0,2,20,2,2,所以答案为 44。