Cow Hopscotch

Interview

Time limit1sMemory limit256 MB

Summary

Count paths from the top-left cell to the bottom-right cell that move strictly down and right onto cells of the opposite color.

Level: Medium4 of 10
Topics: Dynamic programming, Matrix
Solved: No attempts yet

Problem

People play hopscotch, and Farmer John's cows have come up with a variant of the game for themselves. The players are clumsy animals that weigh close to a ton, so cow hopscotch almost always ends in a mess, yet the cows still set up a game nearly every afternoon.

The board is an $R$ by $C$ grid ( $2 \le R \le 15$ , $2 \le C \le 15$ ). Every square is painted red or blue. A cow starts on the top left square and reaches the bottom right square through a sequence of jumps. A jump is valid only when all three conditions hold:

The square you jump to has a different color from the square you are on.
The square you jump to is at least one row below the square you are on.
The square you jump to is at least one column to the right of the square you are on.

Count the sequences of valid jumps that take a cow from the top left square to the bottom right square. Two sequences count as different when the list of visited squares differs anywhere.

Input

The first line contains two integers $R$ and $C$ . Each of the next $R$ lines contains $C$ characters. Each character is R for a red square or B for a blue square.

Output

Print the number of different ways to jump from the top left square to the bottom right square.

Examples5

Example 1
Input
```
4 4
RRRR
RRBR
RBBR
RRRR
```
Expected output
```
3
```
Example 2
Input
```
2 2
RB
RB
```
Expected output
```
1
```
Example 3
Input
```
2 2
RB
BR
```
Expected output
```
0
```
Example 4
Input
```
3 3
RBR
BRB
RBR
```
Expected output
```
0
```
Example 5
Input
```
5 5
BBRBB
RRRRR
BRRBR
BRBBB
RRRRR
```
Expected output
```
9
```