Description

In an $n \times m$ grid, there is an army unit that needs resupply. Each cell in the area is either an empty cell or an obstacle. The air fleet needs to dispatch several transport planes to this area. Each transport plane can drop supplies to two adjacent (sharing a common edge) empty cells. To prevent unnecessary damage, a cell marked as empty can receive at most one drop.

Due to the weather, the exact location of the army unit cannot be determined. Therefore, for every empty cell, when the army unit is in that cell (treat it as an obstacle), the Führer wants to know the number of different schemes to drop any amount of supplies to the remaining empty cells using any number (possibly $0$) of transport planes. Two schemes are different if and only if there exists a cell that is supplied in one scheme but not in the other, or there exist two supplied cells that are supplied by the same plane in one scheme but not so in the other. If you are still unsure, please refer to the explanation for Sample 1.

You need to write a program to compute these values.

Input Format

Line 1: two space-separated positive integers $n, m$ — the number of rows and columns of the grid region. Next $n$ lines: line $i$ contains $m$ space-separated integers $A_{i1}, A_{i2}, \ldots, A_{im}$ — $A_{ij} = 0$ means the cell in row $i$, column $j$ is an empty cell; $A_{ij} = 1$ means the cell is an obstacle.

Output Format

Output $n$ lines. Line $i$ contains $m$ space-separated integers $B_{i1}, B_{i2}, \ldots, B_{im}$ — if the cell in row $i$, column $j$ is an empty cell, then $B_{ij}$ is the number of schemes after turning that cell into an obstacle; otherwise $B_{ij} = 0$. Each answer is taken modulo $10^9+7$.

2 4
0 0 0 0
0 0 0 1

14 13 10 22
15 11 17 0

4 5
0 0 0 1 1
1 0 0 0 1
1 0 0 0 0
0 0 0 0 0

1882 827 1523 0 0
0 1189 791 1529 0
0 1106 979 823 1315
1810 899 1136 1075 1189

Hint

Explanation for Sample 1

Take the empty cell in row $2$, column $1$ as an example. After it is changed into an obstacle, the grid is as follows. Cells marked with o are empty, and cells marked with x are obstacles.

ｏｏｏｏ
ｘｏｏｘ

There are $15$ schemes as shown below. Different colors represent the drop positions of different transport planes.

Constraints

This problem uses bundled tests. The information for each test point is as follows: | Subtask ID | Points | $n$ | $m$ | | :----------: | :----------: | :----------: | :----------: | | $1$ | $10$ | $\le 2$ | $\le 17$ | | $2$ | $8$ | $\le 5$ | $\le 5$ | | $3$ | $6$ | $\le 9$ | $\le 9$ | | $4$ | $9$ | $\le 12$ | $\le 12$ | | $5$ | $17$ | $\le 15$ | $\le 15$ | | $6$ | $17$ | $\le 16$ | $\le 16$ | | $7$ | $33$ | $\le 17$ | $\le 17$ |

For all testdata, $1 \leq n, m \leq 17$, $A_{ij} \in \{0, 1\}$.

Notes

Von allem Anfang an bin ich nur verraten und betrogen worden!

The statement does not fully agree with historical facts.

Credit: https://www.luogu.org/discuss/show?postid=35727

Translated by ChatGPT 5