問題文

縦 $H$ 行 横 $W$ 列のグリッドがあります．上から $i$ 行目 左から $j$ 列目のマスを $(i,j)$ で表します．
o が書いてあるマスに到達すると宝石を1つ受け取り，x が書いてあるマスに到達すると宝石を1つ没収されます．

各 $i,j (1 \leq i \leq H, 1\leq j \leq W)$ について、マス $(i,j)$ の情報が文字 $A_{i,j}$ によって与えられます．

$A_{i,j}$ が o ならば，マス $(i,j)$ に到達した時必ず宝石を1つ受け取り，$A_{i,j}$ が x ならば，マス $(i,j)$ に到達した時必ず宝石を1つ没収されます．

マス $(1,1)$ は必ず宝石がもらえる o マスであることが保証されています．
また，マス $(1,1)$ および マス $(H,W)$ は必ず # マスでないことが保証されています．

Nafmoくんは宝石を $0$ 個持っている状態で，マス $(1,1)$ に到達し宝石を$1$つ受け取りました．
Nafmoくんは右と下の移動を繰り返すことで，マス $(1,1)$ から マス $(H,W)$ まで最短で到達したいです．ただし，Nafmoくんが宝石を没収されるときに，$1$ つも宝石を持っていない状況が生まれる経路は無効とします．
以上の条件を満たす経路の選び方は何通りあるかを求めてください．

13:39追記：# は通ることができません．

入力

$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$ は整数
• $A_{i,j}$ は o，x，# のいずれか
• $A_{1,1} = $ o
• $A_{H,W} \neq $ #

出力

条件を満たす経路の選び方を求めて出力してください．

サンプル

3 3
ooo
o#o
ooo

2

3 3
oox
xxx
xoo

3

3 3
oxx
xxx
xxx

0