Cow Hopscotch

No attempts yetTime limit1sMemory limit256 MB

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 RR by CC grid (2R152 \le R \le 15, 2C152 \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:

  1. The square you jump to has a different color from the square you are on.
  2. The square you jump to is at least one row below the square you are on.
  3. 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 RR and CC. Each of the next RR lines contains CC 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.