0743 - School Load (much bigger!)

問題

太郎君の住んでいるJOI市は，南北方向にまっすぐに伸びる a 本の道路と，東西方向にまっすぐに伸びる b 本の道路により，碁盤の目の形に区分けされている．南北方向の a 本の道路には，西から順に 1, 2, ... , a の番号が付けられている．また，東西方向の b 本の道路には，南から順に 1, 2, ... , b の番号が付けられている．西から i 番目の南北方向の道路と，南から j 番目の東西方向の道路が交わる交差点を (i, j) で表す.

太郎君は，交差点 (1, 1) の近くに住んでおり，交差点 (a, b) の近くのJOI高校に自転車で通っている．自転車は道路に沿ってのみ移動することができる．太郎君は，通学時間を短くするため，東または北にのみ向かって移動して通学している．

太郎君が交差点 (1, 1) から交差点 (a, b) まで，東または北にのみ向かって移動して通学する方法は何通りあるだろうか．太郎君の通学経路の個数 m を 10⁹ + 7 で割ったあまりで求めよ．

入力

入力は1行のみからなり，空白を区切りとして2個の整数 a, b が書かれている．これは，南北方向の道路の本数と，東西方向の道路の本数を表す． a, b は 1 ≤ a, b ≤ 10⁶ をみたす．

出力

太郎君の通学経路の個数 m を 10⁹ + 7 で割った余りのみからなる1行である.

入出力例

入力例1

2 2

出力例1

2

入力例2

5 4

出力例2

35

入力例3

1000 1000

出力例3

965601742

入力例4

1000000 1000000

出力例4

541097174

コメント

知識程度に覚えておくといいかもしれません(工事現場とかがないってことを利用します)。

タグには繰り返し二乗法と書いてありますが、他の方法でも求められます。

(競プロというよりかは数学な気がする)