0236 - School Load(Easy)

時間制限 1 秒 / メモリ制限 256 MB / 得点 3 / Writer root / x 99 / 統計 /

    タグ:
  • DP

TLE
1sec
MLE
256MB
得点
3

問題

太郎君の住んでいる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 を 10007 で割ったあまりで求めよ.

入力

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

出力

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

入出力例

入力例1

2 2

出力例2

2

入力例2

5 4

出力例2

35

入力例3

20 20

出力例3

9429

985525432 通りあるので、これを 10007 で割った余り 9429 を出力する。

入力例4

1000 1000

出力例4

2461