Score : 1100 points
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.
.
and #
.Input is given from Standard Input in the following format:
H W A_1 A_2 \vdots A_H
Print the answer.
2 2 #. .#
15
For example, if we paint the second row black, the grid becomes:
#. ##
3 3 ... ... ...
230
2 4 #... ...#
150
6 7 ....... ....... .#..... ..#.... .#.#... .......
203949910