配点 : $600$ 点

問題文

$N$ 行 $M$ 列のグリッド $A$ があり、はじめ全てのマスに $0$ が書き込まれています。 ここに以下の操作を行います。

• $1 \le i \le N$ を満たす各整数 $i$ に対して、 $A$ の $i$ 行目の左から $0$ 個以上のマスの数字を $1$ にする。
• $1 \le j \le M$ を満たす各整数 $j$ に対して、 $A$ の $j$ 列目の上から $0$ 個以上のマスの数字を $1$ にする。

この手続きによって作ることのできる $A$ の集合を $S$ とします。

0, 1, ? からなる $N$ 行 $M$ 列のグリッド $X$ が与えられます。 ? を 0 か 1 に置き換えて得られるグリッドは $X$ に含まれる ? の総数を $q$ とすると $2^q$ 個ありますが、このうち $S$ の要素であるものはいくつありますか？ 答えは非常に大きくなる場合があるので、 $998244353$ で割った余りを求めてください。

制約

• $N,M$ は整数
• $1 \le N,M \le 18$
• $X$ は 0, 1, ? からなる $N$ 行 $M$ 列のグリッド

入力

入力は以下の形式で標準入力から与えられる。

$N$ $M$

$X_{1,1} X_{1,2} \dots X_{1,M}$

$X_{2,1} X_{2,2} \dots X_{2,M}$

$\vdots$

$X_{N,1} X_{N,2} \dots X_{N,M}$

出力

答えを整数として出力せよ。

2 3
0?1
?1?

6

条件を満たすグリッドは以下の $6$ つです。

011  011  001
010  011  110

001  011  011
111  110  111

5 3
101
010
101
010
101

0

$X$ に ? が存在しない場合も、答えが $0$ である場合もあります。

18 18
??????????????????
??????????????????
??????????????????
??????????????????
??????????????????
??????????????????
??????????????????
??????????????????
??????????????????
??????????????????
??????????????????
??????????????????
??????????????????
??????????????????
??????????????????
??????????????????
??????????????????
??????????????????

462237431

答えを $998244353$ で割った余りを求めることに注意してください。