题目描述

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

输出格式

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

题目大意

开始你有一个全 $0$ 矩阵，你可以随意执行如下操作：

• 选择任意一行，将其从最左端开始的连续一段染成 $1$。
• 选择任意一列，将其从最上端开始的连续一段染成 $1$。

如果一个矩阵可以由此得到，那么这个矩阵被称为好的。

现在你有一个 01? 矩阵 $a$，你需要将所有 ? 替换为 0 或 1，问得到的矩阵中有多少个是好的。答案对 $998244353$ 取模。

$1\le n,m\le 18$。

2 3
0?1
?1?

6

5 3
101
010
101
010
101

0

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

462237431

提示

制約

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

Sample Explanation 1

条件を満たすグリッドは以下の $6$ つです。 011 011 001 010 011 110 001 011 011 111 110 111

Sample Explanation 2

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

Sample Explanation 3

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