D - square1001の通学経路 (square1001's School Road) Editorial /

Time Limit: 2 sec / Memory Limit: 128 MB

問題文

square1001は、毎日歩いて中学校まで通っている。

彼は、左下の交差点 (1,1) に住んでおり、 右上の交差点 (W,H)にある学校まで行く。

ただし、次のような条件がある。

  • 彼は時間短縮のために右か上にしか進まない。
  • 彼はその日、K 個のマスに用事があった。
    • 左下 が(X_i,Y_i) で, 右上が(X_i+1,Y_i+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
問題文担当者：E869120