第６回日本情報オリンピック　予選

2006年12月17日
情報オリンピック日本委員会

問題

太郎君の住んでいるJOI市は， 南北方向にまっすぐに伸びる a 本の道路と， 東西方向にまっすぐに伸びる b 本の道路により， 碁盤の目の形に区分けされている．

南北方向の a 本の道路には， 西から順に 1, 2, ... , a の番号が付けられている． また， 東西方向の b 本の道路には， 南から順に 1, 2, ... , b の番号が付けられている． 西から i 番目の南北方向の道路と， 南から j 番目の東西方向の道路が交わる交差点を (i, j) で表す．

太郎君は， 交差点 (1, 1) の近くに住んでおり， 交差点 (a, b) の近くのJOI高校に自転車で通っている． 自転車は道路に沿ってのみ移動することができる． 太郎君は， 通学時間を短くするため， 東または北にのみ向かって移動して通学している．

現在， JOI市では， n 個の交差点 (x₁, y₁), (x₂, y₂), ... , (x_n, y_n) で工事を行っている． 太郎君は工事中の交差点を通ることができない．

太郎君が交差点 (1, 1) から交差点 (a, b) まで， 工事中の交差点を避けながら， 東または北にのみ向かって移動して通学する方法は何通りあるだろうか． 太郎君の通学経路の個数 m を求めるプログラムを作成せよ．

入力

入力ファイルの1行目には， 空白を区切りとして2個の整数 a, b が書かれている． これは， 南北方向の道路の本数と， 東西方向の道路の本数を表す． a, b は 1 ≦ a, b ≦ 16 をみたす．

2行目には, 工事中の交差点の個数を表す整数 n が書かれている． n は 1 ≦ n ≦ 40 をみたす．

続く n 行 (3行目から n+2 行目) には， 工事中の交差点の位置が書かれている． i+2 行目には空白で区切られた整数 x_i, y_i が書かれており， 交差点 (x_i, y_i) が工事中であることを表す． x_i, y_i は 1 ≦ x_i, y_i ≦ 16 をみたす．

出力

提出する出力ファイルは， 太郎君の通学経路の個数 m だけを含む1行からなる．

例

下図は a=5, b=4, n=3 で， 工事中の交差点が (2,2), (2,3), (4,2) の場合を表している．

この場合， 通学経路は m=5 通りある． 5通りの通学経路を全て図示すると， 以下の通り．

入出力例

5 4
3
2 2
2 3
4 2
   

5
   

※各入出力例のデータは， 右クリック等によりファイルに保存して利用可能です．