C - 経路 Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

横 W x 縦 H のグリッドがあります。左から i 番目、下から j 番目のマス目には (i, j) という番号がついています。

高橋君は、マス目 (i, j) から (i+1, j) または (i, j+1) に進むことができます。高橋君が (1, 1) から (W, H) まで行く経路の個数を 1,000,000,007 で割ったあまりを求めてください。

入力

入力は以下の形式で標準入力から与えられる。

W H
  • 2 ≤ W, H ≤ 10^5 をみたす。

部分点

この問題には部分点が設定されている。満点は 101 点である。
  • W, H ≤ 10 を満たすデータセットに正解した場合は、50 点が与えられる。
  • W, H ≤ 1000 を満たすデータセットに正解した場合は、上記の点数とは別に 50 点が与えられる。

出力

高橋君が (1, 1) から (W, H) まで行く経路の個数を 1,000,000,007 で割ったあまりを出力せよ。 出力の末尾には改行を入れること。

入力例1

4 3

出力例1

10
  • (1, 1) → (1, 2) → (1, 3) → (2, 3) → (3, 3) → (4, 3)
  • (1, 1) → (1, 2) → (2, 2) → (2, 3) → (3, 3) → (4, 3)
  • (1, 1) → (1, 2) → (2, 2) → (3, 2) → (3, 3) → (4, 3)
  • (1, 1) → (1, 2) → (2, 2) → (3, 2) → (4, 2) → (4, 3)
  • (1, 1) → (2, 1) → (2, 2) → (2, 3) → (3, 3) → (4, 3)
  • (1, 1) → (2, 1) → (2, 2) → (3, 2) → (3, 3) → (4, 3)
  • (1, 1) → (2, 1) → (2, 2) → (3, 2) → (4, 2) → (4, 3)
  • (1, 1) → (2, 1) → (3, 1) → (3, 2) → (3, 3) → (4, 3)
  • (1, 1) → (2, 1) → (3, 1) → (3, 2) → (4, 2) → (4, 3)
  • (1, 1) → (2, 1) → (3, 1) → (4, 1) → (4, 2) → (4, 3)
の 10 通りの経路があります。

入力例2

123 456

出力例2

210368064