4473 . 棋盤·續
Description
給你一個 $N \times M$ 的棋盤
這個棋盤可以用 $N$ 個長度為 $M$ 的字串表示
棋盤上的每一格可能是障礙物(表示為x)或是普通格子(表示為o)
令左上角為 $(1,1)$ ，右下角為 $(N,M)$
保證 $(1,1)$ 和 $(N,M)$ 必為普通格子
在這個棋盤上只能往右或往下走 (當然，不能走到障礙物上)
然而，你最多可以可以往左或往上走一格 $K$ 次 (也不能走到障礙物上或棋盤外)
試問有幾種相異的路徑可以從 $(1,1)$ 出發並結束於 $(N,M)$
請將答案模 $10^9 + 7$ 輸出
Input Format
第一行為三個整數 $N,M,K$
接下來 $N$ 行，每行有一字串 $S_i$
Input Limits:
$1 \leq N,M \leq 500$
$0 \leq K \leq 500$
$\forall i, |S_i| = M$
$\forall i,j, S_{ij} \in \{x,o\}$
Output Format
輸出一非負整數
Sample Input 1
3 3 0
ooo
oxo
ooo
ooo
oxo
ooo
Sample Output 1
2
Sample Input 2
2 3 1
ooo
oxo
ooo
oxo
Sample Output 2
5
Hints
Subtasks
| No. | Testdata Range | Score |
|---|
