The contraband game is a game in which players from two teams, the "Northern" and "Southern" countries, attempt to smuggle cash from the opposing country back to their own. The money is arranged in a room with $N\times M$ floor tiles, each tile containing a stack of 100 million yen. The money on the tile that is $i$ rows from the top and $j$ columns from the left, tile $(i,j)$, initially belongs to the Northern team if $G_{i,j}$ is N, or to the Southern team if $G_{i,j}$ is S.

As part of the game, the players must place all of the money into various trunks. Each team is provided with an unlimited number of trunks with a width equal to one floor tile and a length equal to an arbitrary positive integer number of floor tiles. Given that the money on a tile must be placed into the trunk covering that tile, the players are to arrange trunks in the room such that the following conditions are satisfied:

1. Each trunk is placed either horizontally or vertically.
2. Each tile is fully covered by exactly one trunk.
3. Each trunk only contains money belonging to the same team.

Any arrangement of trunks satisfying these conditions is deemed valid. As the organizer of the game, it is imperative that you are able to keep up with its dynamic nature. At any point, the money on a tile might be smuggled, transferring its ownership from one team to the other! As such, you are to compute an array of values $A_{i,j}$, where $A_{i,j}$ denotes the number of different valid arrangements of trunks if the money on tile $(i,j)$ is smuggled to the opposite team. Two arrangements are different if two tiles are covered by the same trunk in one arrangement but not in the other.

Constraints

$1\le N\times M\le 300$

$G_{i,j}$ is either N or S.

Subtask 1 [2/15]

$N=1$

Subtask 2 [6/15]

$1\le N\times M\le 100$

Subtask 3 [7/15]

No additional constraints.

Input Specification

The first line contains $2$ integers $N$ and $M$.

The next $N$ lines each contain a string of length $M$. The $j$-th character in the $i$-th of these strings denotes $G_{i,j}$.

Output Specification

Output $N$ lines, each containing $M$ space-separated integers. The $j$-th integer on the $i$-th line should contain the value of $A_{i,j}$. Since these values could be large, output all of them modulo ${10}^9+7$.

Sample Input 1

2 3
SNN
NSN

Sample Output 1

9 6 1
9 12 4

Sample Input 2

6 8
NNSSSSNN
SNNSSNNS
SSNNNNSS
SSSNNSSS
SSSNNSSS
SSSNNSSS

Sample Output 2

59061611 736255993 67498984 237537811 237537811 67498984 736255993 59061611
195648511 53258468 791854907 500113121 500113121 791854907 53258468 195648511
937727115 454575657 500244687 987096005 987096005 500244687 454575657 937727115
335581721 987380067 478461715 129003842 129003842 478461715 987380067 335581721
984856079 234382826 314896562 160625575 160625575 314896562 234382826 984856079
429208652 783720283 111507071 233399506 233399506 111507071 783720283 429208652