Ex - E or m Editorial /

Time Limit: 4 sec / Memory Limit: 1024 MB

配点 : 600

問題文

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

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

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

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

制約

  • N,M は整数
  • 1 \le N,M \le 18
  • X0, 1, ? からなる NM 列のグリッド

入力

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

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

Score : 600 points

Problem Statement

We have a grid A with N rows and M columns. Initially, 0 is written on every square.
Let us perform the following operation.

  • For each integer i such that 1 \le i \le N, in the i-th row, turn the digits in zero or more leftmost squares into 1.
  • For each integer j such that 1 \le j \le M, in the j-th column, turn the digits in zero or more topmost squares into 1.

Let S be the set of grids that can be obtained in this way.

You are given a grid X with N rows and M columns consisting of 0, 1, and ?.
There are 2^q grids that can be obtained by replacing each ? with 0 or 1, where q is the number of ? in X. How many of them are in S?
This count can be enormous, so find it modulo 998244353.

Constraints

  • N and M are integers.
  • 1 \le N,M \le 18
  • X is a grid with N rows and M columns consisting of 0, 1, and ?.

Input

The input is given from Standard Input in the following format:

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}

Output

Print an integer representing the answer.


Sample Input 1

2 3
0?1
?1?

Sample Output 1

6

The following six grids are in S.

011  011  001
010  011  110

001  011  011
111  110  111

Sample Input 2

5 3
101
010
101
010
101

Sample Output 2

0

X may have no ?, and the answer may be 0.


Sample Input 3

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

Sample Output 3

462237431

Be sure to find the count modulo 998244353.