問題文

$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}$

出力

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

入力例 1

2 3
0?1
?1?

出力例 1

6

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

011  011  001
010  011  110

001  011  011
111  110  111

入力例 2

5 3
101
010
101
010
101

出力例 2

0

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

入力例 3

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

出力例 3

462237431

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