#873 WhiteBlue

Statement

Statement language

You want to paint every cell of an $N \times M$ grid either white or blue. Some cells are already painted, and their colors cannot be changed.

Paint all remaining cells so that no three consecutive cells in a row and no three consecutive cells in a column all have the same color.

Count the number of distinct ways to paint the grid while satisfying this condition.

The input is given in the following format:

$N\ M$ $S_1$ $S_2$

Print the number of valid ways to paint the grid, modulo $1\,000\,000\,007$ .

#	Score	Constraints
1	15	$N \le 2$ , $M \le 6$ .
2	20	$N \le 4$ , .

Sample 1

Input

1 3
...

Output

6

Of the $2^3=8$ paintings, the two monochromatic paintings are invalid.

Sample 2

Input

3 1
W
.
W

Output

1

The middle cell must be blue.

Sample 3

Input

2 3
W..
.B.

Output

9

Sample 4

Input

3 3
WWW
...
...

Output

0