D - square1001の通学経路 (square1001's School Road)
Editorial
/
問題文担当者:E869120
Time Limit: 2 sec / Memory Limit: 128 MB
問題文
square1001は、毎日歩いて中学校まで通っている。
彼は、左下の交差点 (1,1) に住んでおり、 右上の交差点 (W,H)にある学校まで行く。
ただし、次のような条件がある。
- 彼は時間短縮のために右か上にしか進まない。
- 彼はその日、K 個のマスに用事があった。 左下 が(X_i,Y_i) で, 右上が(X_i+1,Y_i+1) のマスである。
そのため、用事のあるマスそれぞれについて、その周りの交差点4つのうち少なくとも1つは通る必要があった。
それらの条件を満たす行き方は何通りあるか。 mod 1,000,000,007で求めよ。
入力
入力は以下の形式で標準入力から与えられる。
H W K X_1 Y_1 X_2 Y_2 : : X_K Y_K
- 1 行目には、整数 H (1≦H≦1,000) , W(1≦W≦1,000) , K(1≦K≦200)が空白区切りで与えられる。
- 次のK 行には、整数 X_i (1≦X_i<W) , 整数 Y_i (1≦Y_i<H)が空白区切りで与えられる。
出力
条件を満たす行き方を1行に出力しなさい。
入力例1
4 4 1 2 2
出力例1
18
(1,1)→(1,2)→(1,3)→(1,4)→(2,4)→(3,4)→(4,4)という行き方と、
(1,1)→(2,1)→(3,1)→(4,1)→(4,2)→(4,3)→(4,4)という行き方はできない。
よって, 20-2=18を出力する。
※図の左上数が抜けていてすみません。
入力例2
9 9 3 3 2 4 5 7 7
出力例2
4380