@everyone 揪打CF
4466 . 棋盤·改
TopCoder
Description
給你一個 $N \times M$ 的棋盤
令左上角為 $(1,1)$ ，右下角為 $(N,M)$
這個棋盤可以用 $N$ 個長度為 $M$ 的字串表示
棋盤上的每一格可能是障礙物(表示為x)、普通格子(表示為o)、傳送門(表示為p)
只要停留在非障礙物的格子，就可以往右或往下走一格(當然，不能走到障礙物上)
另外，如果剛好在傳送門的話，則可以傳送到任何右下方的非障礙物格子
特別的是，也可以走到傳送門而不使用它，而且即便兩種走法經過的格子一樣，經由傳送門和經由一般方式走一格會被視為兩種走法
試問有幾種相異的走法可以從 $(1,1)$ 走到 $(N,M)$
另外我們保證起點和終點都是普通格子
請將答案模$10^8 + 7$輸出
Input Format
第一行為兩個正整數 $N,M$
接下來 $N$ 行，每行有一字串 $S_i$
Input Limits:
$N,M \leq 2000$
$\forall i, |S_i| = M$
$\forall i,j, S_{ij} \in \{x,o,p\}$
Output Format
輸出一非負整數
Sample Input 1
3 3
ooo
oxo
ooo
ooo
oxo
ooo
Sample Output 1
2
Sample Input 2
4 3
opo
oxx
oxo
ooo
opo
oxx
oxo
ooo
Sample Output 2
4
Sample Input 3
1 4
oppo
oppo
Sample Output 3
5
Hints
在範例測資2中，有以下四種路徑
$(1,1) \rightarrow (2,1) \rightarrow (3,1) \rightarrow (4,1) \rightarrow (4,2) \rightarrow (4,3)$
$(1,1) \rightarrow (1,2) \rightarrow (4,2) \rightarrow (4,3)$
$(1,1) \rightarrow (1,2) \rightarrow (3,4) \rightarrow (4,3)$
$(1,1) \rightarrow (1,2) \rightarrow (4,3)$
前五筆測資共佔30分，且不包含任何傳送門
Problem Source
Subtasks
| No. | Testdata Range | Score |
|---|