Monochromization

AtCoder

IDkeyence2020_f

Time2000ms

Memory256MB

Difficulty—

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$ [samples]

Samples

Input #1

2 2
#.
.#

Output #1

15

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

#.
##

Input #2

3 3
...
...
...

Output #2

Input #3

2 4
#...
...#

Output #3

Input #4

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

Output #4

203949910

API Response (JSON)

{
  "problem": {
    "name": "Monochromization",
    "description": {
      "content": "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 ",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "keyence2020_f"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "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 ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments