/ 
実行時間制限: 5 sec / メモリ制限: 1024 MiB
配点 : 1200 点
問題文
長さ 2^N の非負整数列が M 個黒板に書いてあります． i 番目 (1 \leq i \leq M) の数列は A_i=(A_{i,1},A_{i,2},\ldots,A_{i,2^N}) です．
あなたは以下の 2 種類の操作を好きな順番で好きな回数行うことができます．
-
黒板に書かれた数列を 1 つ自由に選び，それを 1 回左シフトしたものを新たに黒板に書き込む． より正確に言えば，数列 x=(x_1,x_2,\ldots,x_{2^N}) を選んだ場合，新たに (x_2,\ldots,x_{2^N},x_1) を書き込む．
-
黒板に書かれた数列を 2 つ（これらが同一でも構わない）を自由に選び，それらの要素ごとのビット単位 \mathrm{XOR} をとった数列を新たに黒板に書き込む． より正確に言えば，数列 x=(x_1,x_2,\ldots,x_{2^N}),y=(y_1,y_2,\ldots,y_{2^N}), を選んだ場合，新たに (x_1 \oplus y_1,x_2 \oplus y_2,\ldots,x_{2^N} \oplus y_{2^N}) を書き込む．
どちらの操作でも，選んだ数列は消えないことに注意してください．
黒板に書き込むことができる数列の種類数を 998244353 で割ったあまりを求めてください．
ビット単位 \mathrm{XOR} 演算とは
非負整数 A, B のビット単位 \mathrm{XOR} 、A \oplus B は、以下のように定義されます。
- A \oplus B を二進表記した際の 2^k (k \geq 0) の位の数は、A, B を二進表記した際の 2^k の位の数のうち一方のみが 1 であれば 1、そうでなければ 0 である。
一般に k 個の非負整数 p_1, p_2, p_3, \dots, p_k のビット単位 \mathrm{XOR} は (\dots ((p_1 \oplus p_2) \oplus p_3) \oplus \dots \oplus p_k) と定義され、これは p_1, p_2, p_3, \dots, p_k の順番によらないことが証明できます。
制約
- 1 \leq N \leq 16
- 1 \leq M \leq 8
- 0 \leq A_{i,j} < 256
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる．
N M
A_{1,1} A_{1,2} \ldots A_{1,2^N}
A_{2,1} A_{2,2} \ldots A_{2,2^N}
\vdots
A_{M,1} A_{M,2} \ldots A_{M,2^N}
出力
答えを出力せよ．
入力例 1
1 1 1 2
出力例 1
4
以下の手順で 4 種類の数列を書き込むことができます．
- 最初，黒板には (1,2) のみが書かれている
- (1,2) と (1,2) を選び \mathrm{XOR} をとることで，(0,0) を書き込むことができる．
- (1,2) を選んで左シフトすることで，(2,1) を書き込むことができる．
- (1,2) と (2,1) を選び \mathrm{XOR} をとることで，(3,3) を書き込むことができる．
入力例 2
1 2 1 1 1 2
出力例 2
8
入力例 3
2 4 12 4 11 15 0 6 4 0 8 5 4 8 2 8 8 13
出力例 3
32768
入力例 4
4 5 55 153 189 168 81 18 15 140 3 101 113 216 215 67 113 81 42 47 89 86 51 230 108 163 251 112 246 238 160 176 37 169 63 215 220 47 148 158 76 112 140 210 14 125 222 217 120 127 159 238 73 195 112 141 239 109 175 82 191 20 95 46 6 165 156 37 120 73 189 235 107 167 184 42 29 136 219 237 232 212
出力例 4
8247623