← 返回题目列表

AtCoder · arc046_d

D. 兔子和格子

中文机器翻译题面 查看原题

問題文

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 后的余数。