Grid Coloring

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.

Medium7Dynamic programmingCombinatoricsMathNo attempts yetTime limit1sMemory limit512 MB

Description

Examples3

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