F - Monochromization Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 1100 点

問題文

H \times W のマス目があり、各マスは初期状態で白または黒に塗られています。 初期状態における各マスの塗られ方を表す文字列 A_1, A_2, ..., A_H が与えられます。 これらの文字列は、各 (i, j) (1 \leq i \leq H, 1 \leq j \leq W) について、 文字列 A_i の j 文字目が . ならば i 行 j 列のマスは白に、 # ならば i 行 j 列のマスは黒に塗られていることを表します。

このマス目の各マスの白または黒による塗られ方 (全部で 2^{HW} 個あります) であって、 初期状態から以下の操作を好きな順番で好きな回数 (0 回以上) 繰り返して得られるものの個数を 998 244 353 で割ったあまりを求めてください。

  • ある行を一つ選び、その行に含まれるすべてのマスを白く塗る。
  • ある行を一つ選び、その行に含まれるすべてのマスを黒く塗る。
  • ある列を一つ選び、その列に含まれるすべてのマスを白く塗る。
  • ある列を一つ選び、その列に含まれるすべてのマスを黒く塗る。

制約

  • 1 \leq H, W \leq 10
  • |A_i| = W (1 \leq i \leq H)
  • すべての A_i は文字 . と文字 # だけからなる。
  • H および W は整数である。

入力

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

H W
A_1
A_2
\vdots
A_H

出力

答えを出力せよ。

入力例 1

2 2
#.
.#

出力例 1

15

たとえば、2 行目を黒く塗って得られるマス目は以下のとおりです。

#.
##

入力例 2

3 3
...
...
...

出力例 2

230

入力例 3

2 4
#...
...#

出力例 3

150

入力例 4

6 7
.......
.......
.#.....
..#....
.#.#...
.......

出力例 4

203949910

Score : 1100 points

Problem Statement

We have an H \times W grid, where each square is painted white or black in the initial state. Given are strings A_1, A_2, ..., A_H representing the colors of the squares in the initial state. For each pair (i, j) (1 \leq i \leq H, 1 \leq j \leq W), if the j-th character of A_i is ., the square at the i-th row and j-th column is painted white; if that character is #, that square is painted black.

Among the 2^{HW} ways for each square in the grid to be painted white or black, how many can be obtained from the initial state by performing the operations below any number of times (possibly zero) in any order? Find this count modulo 998,244,353.

  • Choose one row, then paint all the squares in that row white.
  • Choose one row, then paint all the squares in that row black.
  • Choose one column, then paint all the squares in that column white.
  • Choose one column, then paint all the squares in that column black.

Constraints

  • 1 \leq H, W \leq 10
  • |A_i| = W (1 \leq i \leq H)
  • All strings A_i consist of . and #.
  • H and W are integers.

Input

Input is given from Standard Input in the following format:

H W
A_1
A_2
\vdots
A_H

Output

Print the answer.

Sample Input 1

2 2
#.
.#

Sample Output 1

15

For example, if we paint the second row black, the grid becomes:

#.
##

Sample Input 2

3 3
...
...
...

Sample Output 2

230

Sample Input 3

2 4
#...
...#

Sample Output 3

150

Sample Input 4

6 7
.......
.......
.#.....
..#....
.#.#...
.......

Sample Output 4

203949910