788 . 走迷宮
TopCoder
Description
在代達羅斯建造的迷宮中，有個區域是被下了神秘魔法的方陣，高為 $N$，寬為 $M$，入口在左上角，而出口是個會隨日期變化的傳送門，以 $Q$ 天為一個變化週期。因為此地的魔法規則，每次移動只能往右或往下移動一格。方陣中有些地方會有石柱，它們會擋住去路。伊卡洛斯今天很無聊，想請你計算在各個日期中，從入口走到出口的方式有幾種。
Input Format
第一行有三個數字 $N,M,Q$，代表方陣的高、寬、出口變化的週期。
接下來 $N$ 行，每行有 $M$ 個屬於 ${0,1}$ 的數字，$1$ 代表這個位置有石柱，反之則無。入口一定沒有石柱。
再接下來 $Q$ 行，每行有 $2$ 個數字 $x_i,y_i$，代表第 $i$ 天的出口座標，$x_i$ 是縱座標，由上往下遞增；$y_i$ 是橫座標，由左往右遞增。
- $1 \le N,M \le 1000$
- $1 \le Q \le 10^ 5$
- $0 \le x_i < N,\forall i$
- $0 \le y_i < M,\forall i$
Output Format
$Q$ 行，每行輸出當天走到出口的方法數除以 $10^ 9 + 7$ 的餘數。
Sample Input 1
2 3 1
0 0 1
0 0 0
1 2
0 0 1
0 0 0
1 2
Sample Output 1
2
Sample Input 2
3 3 2
0 0 0
0 1 0
0 0 0
2 1
2 2
0 0 0
0 1 0
0 0 0
2 1
2 2
Sample Output 2
1
2
2
Hints
Problem Source
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~1 | 範例測資 | 0 |
| 2 | 0~13 | 無額外限制 | 100 |