配点 : 100 点
問題文
(1,2,\dots,N) 的排列有 M 个。 第i 个排列是 P_i = (P_{i,1},P_{i,2},\dots,P_{i,N}) 。
你有一个数列 Q=(1,2,\dots,N) 。并且,你可以进行以下操作 0 次或更多次。
- 1 \le i \le M 满足的整数 i ,选择并Q 在 (Q_{P_{i,1}},Q_{P_{i,2}},\dots,Q_{P_{i,N}}) 更新为。
操作后的 Q 所有可能的数列的逆序数总和 998244353 取余。起初,数列
制約
- 1 \le N \le 30
- 1 \le M \le 30
- P_i=(P_{i,1},P_{i,2},\dots,P_{i,N}) 是 给出了 (1,2,\dots,N) 的排列
部分点
针对此问题设置了部分分数。 满足
- N \le 6 满足的数据集中的正确答案情况 10 点。
入力
输入是按以下格式从标准输入给出的。
N M
P_{1,1} P_{1,2} \dots P_{1,N}
P_{2,1} P_{2,2} \dots P_{2,N}
\vdots
P_{M,1} P_{M,2} \dots P_{M,N}
出力
打印答案。
入力例 1
3 2 1 2 3 2 3 1
出力例 1
4
你能够得到的数列个数为 Q 是 给出了 (1,2,3),(2,3,1),(3,1,2) 的 3 个。每个的翻转数为 0,2,2 所以答案是 0 + 2 + 2 = 4 。
入力例 2
5 2 3 4 5 1 2 1 5 4 3 2
出力例 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
出力例 3
701414999