迷路 Go編（paizaランク B 相当）

問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！

問題

下記の問題をプログラミングしてみよう！

横 N マス縦 M マスの敷地があり、左から A 番目、上から B 番目のマスは(A, B) と表現します。また、敷地にはブロックが B 個置かれています。(X_i, Y_i) はブロックがあり、このマスへは移動することができません。
あなたは現在スタート( 1, 1 )におり、ゴール(N, M) へ行こうと考えています。また、(A, B) から移動できるマスは(A + 1, B) または(A, B + 1 )のみです(当然、ブロックのあるマスへは移動できません)。

スタートからゴールまで行く方法は何通りありますか？答えは非常に大きくなることがあるので、 1,000,000,007 で割ったあまりを出力してください。

入力される値

N M B
X_1 Y_1
X_2 Y_2
...
X_B Y_B

・ 1 行目に、敷地の横のマス数と縦のマス数とブロックの数が空白区切りで与えられます。
・ 2 行目から B + 1 行にかけて、ブロックの位置が与えられます。

入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。標準入力からの値取得方法はこちらをご確認ください

期待する出力: スタートからゴールまで行く方法は何通りか答えてください。スタートからゴールまで行く方法が存在しない場合は 0 を出力してください。答えは非常に大きくなることがあるので、 1,000,000,007 で割ったあまりを出力してください。

また、末尾に改行を入れ、余計な文字、空行を含んではいけません。

条件: すべてのテストケースにおいて、以下の条件をみたします。

・ 1 ≦ N, M ≦ 1,000
・ 0 ≦ B ≦ N + M - 2
・ 1 ≦ X_i ≦ N
・ 1 ≦ Y_i ≦ M
・ (X_i, Y_i) ≠ ( 1, 1 ) かつ (X_i, Y_i) ≠ (N, M)

入力例1: 3 4 2
2 1
1 3

出力例1: 3

入力例2: 3 4 2
2 1
1 3

出力例2: 3

問題一覧へ戻る