Grid Coloring

Time limit1sMemory limit512 MB

Summary

Count completions of an m by n red/blue grid where every blue cell forces the whole prefix rectangle from the top left corner to be blue.

Level: Medium7 of 10
Topics: Dynamic programming, Combinatorics, Math
Solved: No attempts yet

Problem

You want to color every square of a grid with $m$ rows and $n$ columns either red or blue. The coloring must satisfy all of the following.

Every square is colored.
Some squares already have a color, and that color cannot be changed.
For every blue square, all squares in the rectangle whose opposite corners are the top left square of the grid and that square are blue as well.

Count the distinct colorings that satisfy these conditions. The grid cannot be rotated.

Input

The first line contains two space separated integers $m$ and $n$ ( $1 \le m, n \le 30$ ).

Each of the next $m$ lines contains $n$ characters describing the grid. The character B marks a square already colored blue, R marks a square already colored red, and . marks a square that is not colored yet.

Output

Print the number of distinct colorings on a single line.

Hint

The 6 colorings of the first example are:

BB   BB   BR   BR   BB   BB
BB   BR   BR   BR   BR   BB
BR   BR   BR   RR   RR   RR

Examples3

Example 1
Input
```
3 2
..
B.
.R
```
Expected output
```
6
```

Example 2

Input

7 6
......
.....B
.B..R.
......
...B..
.R....
...R..

Expected output

Example 3
Input
```
2 2
R.
.B
```
Expected output
```
0
```