問題文
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