Problem Background

The chilling wind in Moscow / Reminds me of yesterday's dream / Ah, will you still remember me?

December 1941.

The biting cold, the exhausted troops... The plan to encircle the capital has hit a snag. The air force might be the last hope to save the situation, thought the leader Adolf.

Problem Description

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

Due to weather conditions, the exact location of the army unit cannot be determined. Therefore, the leader wants to know, for each empty cell, the number of different schemes to drop supplies to the remaining empty cells using several (possibly zero) transport planes when that cell is considered an obstacle. Two schemes are considered different if there exists a cell that is supplied in one scheme but not in the other, or if there are two supplied cells that are supplied by the same plane in one scheme but not in the other. If in doubt, please refer to the explanation of Sample 1.

You need to write a program to help the leader calculate these values.

Input Format

The first line: Two space-separated positive integers $n, m$ — the number of rows and columns of the grid area.

The next $n$ lines: The $i$-th line contains $m$ space-separated integers $A_{i1}, A_{i2}, \ldots, A_{im}$ — where $A_{ij} = 0$ indicates that the cell at the $i$-th row and $j$-th column is empty; $A_{ij} = 1$ indicates that the cell is an obstacle.

Output Format

Output $n$ lines, the $i$-th line contains $m$ space-separated integers $B_{i1}, B_{i2}, \ldots, B_{im}$ — if the cell at the $i$-th row and $j$-th column is empty, $B_{ij}$ is the number of schemes to drop supplies when that cell becomes an obstacle; otherwise, $B_{ij} = 0$. Each answer should be modulo $10^9+7$.

Sample Input and Output

Input Sample #1

2 4
0 0 0 0
0 0 0 1

Output Sample #1

14 13 10 22
15 11 17 0

Input Sample #2

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

Output Sample #2

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

Notes

Explanation of Sample 1

Taking the empty cell at the 2nd row and 1st column as an example, the grid when it becomes an obstacle is shown below, where 'o' represents an empty cell and 'x' represents an obstacle.

ｏｏｏｏ
ｘｏｏｘ

The 15 schemes are illustrated below, with different colors representing different planes' drop locations.

Data Size and Constraints

This problem uses bundled testing, with the following test points information:

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

Notes

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

The problem statement does not fully align with historical facts.

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

见题面 Input 部分

见题面 Output 部分