問題文

(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 点が与えられる。

入力例 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