[ABC295Ex] E or m

开始你有一个全 $0$ 矩阵，你可以随意执行如下操作： - 选择任意一行，将其从最左端开始的连续一段染成 $1$。 - 选择任意一列，将其从最上端开始的连续一段染成 $1$。 如果一个矩阵可以由此得到，那么这个矩阵被称为好的。 现在你有一个 `01?` 矩阵 $a$，你需要将所有 `?` 替换为 `0` 或 `1`，问得到的矩阵中有多少个是好的。答案对 $998244353$ 取模。 $1\le n,m\le 18$。

[problemUrl]: https://atcoder.jp/contests/abc295/tasks/abc295_h $ 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} $

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

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 $ で割った余りを求めることに注意してください。