TopCoder

User's AC Ratio

100.0% (4/4)

Submission's AC Ratio

83.3% (5/6)

Tags

Description

在代達羅斯建造的迷宮中,有個區域是被下了神秘魔法的方陣,高為 N,寬為 M,入口在左上角,而出口是個會隨日期變化的傳送門,以 Q 天為一個變化週期。因為此地的魔法規則,每次移動只能往右或往下移動一格。方陣中有些地方會有石柱,它們會擋住去路。伊卡洛斯今天很無聊,想請你計算在各個日期中,從入口走到出口的方式有幾種。

Input Format

第一行有三個數字 N,M,Q,代表方陣的高、寬、出口變化的週期。
接下來 N 行,每行有 M 個屬於 0,1 的數字,1 代表這個位置有石柱,反之則無。入口一定沒有石柱。
再接下來 Q 行,每行有 2 個數字 xi,yi,代表第 i 天的出口座標,xi 是縱座標,由上往下遞增;yi 是橫座標,由左往右遞增。

  • 1N,M1000
  • 1Q105
  • 0xi<N,i
  • 0yi<M,i

Output Format

Q 行,每行輸出當天走到出口的方法數除以 109+7 的餘數。

Sample Input 1

2 3 1
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

Sample Output 2

1
2

Hints

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0~13 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 2000 524288 65536 1 2
1 2000 524288 65536 1 2
2 2000 524288 65536 2
3 2000 524288 65536 2
4 2000 524288 65536 2
5 2000 524288 65536 2
6 2000 524288 65536 2
7 2000 524288 65536 2
8 2000 524288 65536 2
9 2000 524288 65536 2
10 2000 524288 65536 2
11 2000 524288 65536 2
12 2000 524288 65536 2
13 2000 524288 65536 2