Problem Statement

There is a grid with $H$ rows and $W$ columns. The cell in the $i$-th row from the top and the $j$-th column from the left is denoted by $(i,j)$.
When you reach a cell with o written on it, you receive 1 jewel, and when you reach a cell with x written on it, 1 jewel is confiscated.

For each $i,j (1 \leq i \leq H, 1\leq j \leq W)$, the information of cell $(i,j)$ is given by a character $A_{i,j}$.

If $A_{i,j}$ is o, you always receive 1 jewel when you reach cell $(i,j)$, and if $A_{i,j}$ is x, 1 jewel is always confiscated when you reach cell $(i,j)$.

It is guaranteed that cell $(1,1)$ is an o cell, where a jewel is always received.
It is also guaranteed that neither cell $(1,1)$ nor cell $(H,W)$ is a # cell.

Nafmo, holding $0$ jewels, reached cell $(1,1)$ and received $1$ jewel.
Nafmo wants to travel from cell $(1,1)$ to cell $(H,W)$ along a shortest route by repeatedly moving right and down. However, a route is invalid if a situation arises where Nafmo does not have even $1$ jewel when a jewel is to be confiscated.
Find the number of ways to choose a route satisfying the above conditions.

Added at 13:39: # cells cannot be passed through.

Input

$H \ W$
$A_{1,1}A_{1,2}\dots A_{1,W}$
$\ \vdots$
$A_{H,1}A_{H,2}\dots A_{H,W}$

• $2 \leq H,W \leq 10$
• $H,W$ are integers
• $A_{i,j}$ is one of o, x, #
• $A_{1,1} = $ o
• $A_{H,W} \neq $ #

Output

Output the number of ways to choose a route satisfying the conditions.

Sample

3 3
ooo
o#o
ooo

2

3 3
oox
xxx
xoo

3

3 3
oxx
xxx
xxx

0