Given a grid with ~N~ rows and ~M~ columns, some cells in the grid are blocked, while other cells are empty. Bob has an infinite number of dominos and he wants to place his dominos into the grid. Each domino will occupy ~2 \times 1~ or ~1 \times 2~ cells, where the two cells must be both empty and be adjacent by sharing a common edge. Bob can place any number of dominos (maybe just 0), but dominos placed in the grid cannot overlap.

Bob will also place a flag in the grid, which takes one empty cell. The flag will be treated as a blocked cell. Bob hasn't determined which cell he wants to put his flag. He wants you to write a program to find out the number of different ways to place dominos, if he puts his flag in each cell ~(r, c)~. Since the answer is very huge, output the answer ~\bmod 10^9+7~. If the cell where Bob wants to place flag is blocked, output ~0~.

Input Specification

The first line of input contains two integers ~N~ and ~M~, (~1 \le N, M \le 17~), the number of rows and columns of the grid.

Each of the following ~N~ lines contains ~M~ integers, ~a_{ij}~ (~a_{ij}~ is either ~0~ or ~1~), indicating that the cell ~(i, j)~ is empty if ~a_{ij} = 0~, or blocked if ~a_{ij}=1~.

Output Specification

Output ~N~ lines, and each line contains ~M~ integers ~b_{ij}~, the number of ways to place dominos if Bob places his flag in the cell ~(i, j)~. Since the answer is very huge, output the answer ~\bmod 10^9+7~. If the cell where Bob wants to place flag is blocked, output ~0~.

Constraints

Subtask	Points	Additional constraints
~1~	~10~	~N \le 2~.
~2~	~8~	~N, M \le 5~.
~3~	~6~	~N, M \le 9~.
~4~	~9~	~N, M \le 12~.
~5~	~17~	~N, M \le 15~.
~6~	~20~	~N, M \le 16~.
~7~	~30~	No additional constraints.

Sample Input

2 4
0 0 0 0
0 0 0 1

Sample Output

14 13 10 22
15 11 17 0

Explanation for Sample

If Bob places his flag at the cells ~(r=2, c=1)~, the gird is shown in the following picture.

There are ~15~ different ways to place dominos, shown as following picture.