시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB226627.273%

문제

One day, $\color{blue}{\text{LaLa}}$ realized that she ran out of $\color{red}{\text{m}} \color{brown}{\text{a}} \color{orange}{\text{g}} \color{blue}{\text{i}} \color{magenta} {\text{c}}$ stone components for her $\color{red}{\text{m}} \color{brown}{\text{a}} \color{orange}{\text{g}} \color{blue}{\text{i}} \color{magenta} {\text{c}}$ tools. (Think of them as a battery in our world.) So $\color{blue}{\text{LaLa}}$ rushed to a nearby store and bought a slab of $\color{red}{\text{m}} \color{brown}{\text{a}} \color{orange}{\text{g}} \color{blue}{\text{i}} \color{magenta} {\text{c}}$ stone.

$\color{blue}{\text{LaLa}}$ wants to cut the slab into $\color{red}{\text{m}} \color{brown}{\text{a}} \color{orange}{\text{g}} \color{blue}{\text{i}} \color{magenta} {\text{c}}$ stone components. The slab consists of $N \times M$ cells. Unfortunately, some cells are incompatible with $\color{blue}{\text{LaLa}}$'s $\color{red}{\text{m}} \color{brown}{\text{a}} \color{orange}{\text{g}} \color{blue}{\text{i}} \color{magenta} {\text{c}}$ tools.

The required $\color{red}{\text{m}} \color{brown}{\text{a}} \color{orange}{\text{g}} \color{blue}{\text{i}} \color{magenta} {\text{c}}$ stone component is a 7-cell U-shaped piece.

As $\color{blue}{\text{LaLa}}$ forgot to buy $\color{red}{\text{m}} \color{brown}{\text{a}} \color{orange}{\text{g}} \color{blue}{\text{i}} \color{magenta} {\text{c}}$ stone glue, $\color{blue}{\text{LaLa}}$ can't merge smaller pieces to form the required shape.

Furthermore, since $\color{blue}{\text{LaLa}}$ hates wasting $\color{red}{\text{m}} \color{brown}{\text{a}} \color{orange}{\text{g}} \color{blue}{\text{i}} \color{magenta} {\text{c}}$ stones, $\color{blue}{\text{LaLa}}$ will be satisfied if and only if the slab is cut so that every single compatible cell belongs to a required shape.

Write a program that computes the number of ways to cut the slab so that $\color{blue}{\text{LaLa}}$ is satisfied, modulo $998\,244\,353$. Two ways to cut pieces are different if and only if there exist two compatible cells such that they belong to the same piece in one and to different pieces in the other.

입력

The input is given in the following format:

$N$ $M$

$S_0$

$S_1$

$\vdots$

$S_{N-1}$

where $N$ is the number of rows of the slab, $M$ is the number of columns, and $S_i$ is a binary string of length $M$ where $j$-th character is '1' if and only if the cell at the $i$-th row from the top and $j$-th column from the left is incompatible.

The input satisfies the following constraints:

  • $N$ and $M$ are integers.
  • $3 \le N, M \le 1\,000$

출력

The output should be a integer equal to the number of ways to cut the slab so that $\color{blue}{\text{LaLa}}$ is satisfied, modulo $998\,244\,353$.

예제 입력 1

4 4
0001
0000
0000
1000

예제 출력 1

2

예제 입력 2

5 4
0001
0101
0000
1010
1000

예제 출력 2

1

노트

The following illustrates two possible ways to cut the slab in the first sample.

The following illustrates the only way to cut the slab in the second sample.