問題文

横 $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