Counting Supply Drop Configurations in a Grid

In an (n \times m) grid, each cell is either empty or an obstacle. An army unit is awaiting supplies but its exact location in the empty cells is not known due to bad weather. To supply the unit, an air fleet may dispatch any number (possibly zero) of transport planes. Each transport plane may drop supplies simultaneously on exactly two adjacent (sharing a common side) empty cells. However, to avoid unnecessary damage, every empty cell can receive supplies at most once.

The twist is that the actual location of the army unit is uncertain. For every empty cell, if we assume that the army unit is there then that cell is treated as an obstacle, and supplies will be dropped on some (possibly none) of the remaining empty cells according to the rules above. Two supply drop configurations are considered different if and only if there exists at least one cell that receives a drop in one configuration but not in the other, or there exist two cells which are supplied by the same transport plane in one configuration but by two different planes in the other configuration.

Your task is to calculate, for every originally empty cell, the number of different supply drop configurations when the army unit is assumed to be in that cell. Since the number of configurations may be huge, output the answer modulo (10^9+7).

A configuration is defined by a set of transport plane drops (each drop covers two adjacent empty cells) such that no cell is used more than once. Note that using zero transport planes (i.e. not dropping any supplies) is a valid configuration.

Input Format: Described below.

Note: If you have any doubts, please refer to the explanation of Sample 1.

inputFormat

Input Format: The first line contains two integers (n) and (m) (the number of rows and columns respectively). Each of the next (n) lines contains a string of length (m) consisting of characters '.' and '#' where '.' denotes an empty cell and '#' denotes an obstacle.

It is guaranteed that the grid contains at least one empty cell. (n) and (m) will be small enough (for example, (n\times m\le 16)) so that your program can run in time.

outputFormat

Output Format: Output (n) lines, each containing (m) space-separated integers. For each cell, if the cell is originally empty, output the number of supply drop configurations (modulo (10^9+7)) when that cell is treated as an obstacle (i.e. the assumed location of the army unit). For cells that are originally obstacles, output 0.

sample

2 2
..
..

3 3
3 3