← 返回题目列表

AtCoder · s8pc_1_d

D. square1001的学校路

中文机器翻译题面 查看原题

問題文

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

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