身為一位生活在現代的小偷，學會避開監視器行竊根本是基本操作。但是除了避開監視器外，顯然還需要考慮所謂行竊的流暢度，也就是說要偷就要走最短路徑，降低被發現的風險。而 Kenny 是一位剛入行的純潔新人，還不明白這麼高端的操作，但他真的很想在某復X中學獲得人生中的第一次成就。
而你身為一位消息靈通的資訊人才，獲得復X中學的監視器分布根本小事一件。但光是獲得分布圖還不夠， Kenny 還希望你可以告訴他能避開監視器的最短路徑有多少條，這樣他才知道他偷成功的機率到底有多高。
現在假設復X中學是一個 $m \times n$ 的格狀方陣，而且只能踩在格子上，而校園總共有 $a$ 支監視器，分別在格子 $(x_i, y_i)$ 上。並且 Kenny 必從格子 $(0, 0)$ 出發，偷竊目標必在格子 $(n-1, m-1)$ 上，且已知復X中學的監視器畫質真的爛，所以只要避開監視器所在的格子即可，請你找出最短路徑的條數。
本題為多筆測資輸入。
第一行輸入三個非負整數 $n, m, a$ 。 $(1 \le n, m \le 5000, 0 \le a \le n \times m)$
接下來有 $a$ 行，每行有兩個非負整數，分別為 $x_i, y_i$ 。
輸出一非負整數表示從出發點到目標物並避開監視器的最短路徑個數，答案有可能很大，請 $mod$ $1000000007$。
4 4 0 5 5 5 2 3 2 2 1 4 0 1 4 1
20 9
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |
|||||