LaLa and Magic Stone

One day, \color{blue}{\text{LaLa}} realized that she ran out of magic stone components for her magic 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 magic stone.

\color{blue}{\text{LaLa}} wants to cut the slab into magic stone components. The slab consists of $N \\times M$ cells. Unfortunately, some cells are incompatible with LaLa's magic tools.

The required magic stone component is a 7-cell U-shaped piece.

LaLa forgot to buy magic stone glue, so smaller pieces cannot be merged to form the required shape.

Also, LaLa hates wasting magic stones, so LaLa is satisfied if and only if the slab is cut so that every compatible cell belongs to a required shape.

Write a program that computes the number of ways to cut the slab so that 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$ whose $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 is a single integer equal to the number of ways to cut the slab so that LaLa is satisfied, modulo $998\\,244\\,353$.

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.