C - 経路
解説
/ 
高橋君は、マス目 (i, j) から (i+1, j) または (i, j+1) に進むことができます。高橋君が (1, 1) から (W, H) まで行く経路の個数を 1,000,000,007 で割ったあまりを求めてください。
/ 
実行時間制限: 2 sec / メモリ制限: 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)
入力例2
123 456
出力例2
210368064