#joi2010yoe. [joi2010yo_e]通勤経路
[joi2010yo_e]通勤経路
問題
JOI さんが住むカナダのある都市は,南北方向にまっすぐに伸びる 本の道路と,東西方向にまっすぐに伸びる 本の道路により,碁盤の目の形に区分けされている.
南北方向の 本の道路には,西から順に の番号が付けられている.また,東西方向の 本の道路には,南から順に の番号が付けられている.西から 番目の南北方向の道路と,南から 番目の東西方向の道路が交わる交差点を () で表す.
JOI さんは,交差点 () の近くに住んでおり,交差点 の近くの会社に車で通っている.車は道路に沿ってのみ移動することができる.JOI さんは,通勤時間を短くするため,東または北にのみ向かって移動して通勤している.また,この都市では,交通事故を減らすために,次のような交通規則が設けられている:
- 交差点を曲がった車は,その直後の交差点で曲がることは出来ない.
すなわち,交差点で曲がったあとに ブロックだけ進んで再び曲がることは許されない.このとき,JOI さんの通勤経路は何通り考えられるだろうか.
と が与えられたとき,JOI さんの通勤経路の個数を で割った余りを出力するプログラムを作成せよ.
入力
入力は 行からなり,空白を区切りとして 個の整数 (,) が書かれている. は南北方向の道路の本数, は東西方向の道路の本数を表す.
出力
出力は,JOI さんの通勤経路の個数を で割った余りだけを含む 行からなる.
入力例 1
3 4
出力例 1
5
入力例 において,JOIさんの通勤経路は図のように 通り考えられる.したがって, を出力する.
入力例 2
15 15
出力例 2
43688
入力例 において,JOIさんの通勤経路は 通り考えられる.したがって, を で割った余りである を出力する.