內容
彭羅正對未來進行占卜。他的占卜工具是一個映照宇宙星辰的$n\times m$棋盤。
占卜一開始，彭羅會將代表自己的棋子放在最左上角$(0,0)$的位置，然後他會進行一系列的移動。每次移動，彭羅可以向右或向下移動一格，直到他到達棋盤的最右下角$(n-1,m-1)$的位置。彭羅必須知道總共有多少種不同的移動方式，才能進行準確的占卜。
此外，棋盤上還有$k$個格子映照著宇宙中的黑洞，彭羅的棋子不能踏入這些格子。
請幫助彭羅計算總共有多少種不同的移動方式。
輸入說明
輸入第一行包含三個整數$n,m,k$，分別代表棋盤有幾行、幾列，以及宇宙有幾個黑洞。
接下來$k$行，每行包含兩個整數$x,y$，代表第$x$行第$y$列的格子是黑洞。
- $1 \leq n,m \leq 10^5$
- $0 \leq k \leq\min(nm, 2000)$
- $0 \leq x < n$
- $0 \leq y < m$
Subtask:
- 30%: $n,m \leq 2000$
- 70%: 無其他限制。
輸出說明
輸出一個整數，代表彭羅的棋子從左上角移動到右下角的方法數除以$10^9+7$的餘數。
範例輸入
#1
5 5 4 1 1 2 4 3 3 4 0
範例輸出
#1
6
測資資訊：
記憶體限制：
64
MB
公開 測資點#0 (10%): 1.0s , <1K
公開 測資點#1 (10%): 1.0s , <1M
公開 測資點#2 (10%): 1.0s , <1M
公開 測資點#3 (10%): 1.0s , <1M
公開 測資點#4 (10%): 1.0s , <1M
公開 測資點#5 (10%): 1.0s , <1M
公開 測資點#6 (10%): 1.0s , <1M
公開 測資點#7 (10%): 1.0s , <1M
公開 測資點#8 (10%): 1.0s , <1M
公開 測資點#9 (10%): 1.0s , <1M
公開 測資點#0 (10%): 1.0s , <1K
公開 測資點#1 (10%): 1.0s , <1M
公開 測資點#2 (10%): 1.0s , <1M
公開 測資點#3 (10%): 1.0s , <1M
公開 測資點#4 (10%): 1.0s , <1M
公開 測資點#5 (10%): 1.0s , <1M
公開 測資點#6 (10%): 1.0s , <1M
公開 測資點#7 (10%): 1.0s , <1M
公開 測資點#8 (10%): 1.0s , <1M
公開 測資點#9 (10%): 1.0s , <1M
提示 ：
標籤:
出處:
明達
[管理者：
]
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |
|||||