AtCoder Regular Contest 046

D - うさぎとマス目


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB

問題文

H 行、W 列のマス目があります。第 i (0≦i≦H-1) 行、第 j (0≦j≦W-1) 列のマスを (i,\ j) と表します。

最初、マス (0,\ 0) にうさぎがいます。うさぎは以下の操作を繰り返します。

  • 今いるマスに色が塗られていれば、操作を終了する。
  • 今いるマスに色が塗られていなければ、今いるマスに色を塗り、今いるマス (i,\ j) から ((i+1)\ {\rm mod}\ H,\ j) または (i,\ (j+1)\ {\rm mod}\ W) へ移動する。

うさぎがすべてのマスに色を塗った後、マス (0,\ 0) で操作を終了するような方法は何通りでしょうか? 10^9+7 で割った余りを求めてください。

ただし、うさぎの辿った経路が異なるとき、またそのときのみ、2 つの方法は異なるものとします。


入力

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

H W
  • 1 行目には、マス目の行数 H (2≦H≦10^6) と列数 W (2≦W≦10^6) が空白区切りで与えられる。

出力

答えを 10^9+7 で割った余りを出力せよ。出力の末尾には改行を入れること。


入力例1

2 2

出力例1

2

図の 2 通りです。


入力例2

6 3

出力例2

3

入力例3

3 4

出力例3

0

入力例4

10 10

出力例4

260

入力例5

200 300

出力例5

551887980

答えを 10^9+7 で割った余りを出力してください。


Submit提出する