第９回日本情報オリンピック　予選５

2009年12月13日
情報オリンピック日本委員会

問題

JOIさんが住むカナダのある都市は，南北方向にまっすぐに伸びる w 本の道路と，東西方向にまっすぐに伸びる h 本の道路により，碁盤の目の形に区分けされている．

南北方向の w 本の道路には，西から順に 1, 2, ... , w の番号が付けられている．また，東西方向の h 本の道路には，南から順に 1, 2, ... , h の番号が付けられている．西から i 番目の南北方向の道路と，南から j 番目の東西方向の道路が交わる交差点を (i, j) で表す．

JOIさんは，交差点 (1, 1) の近くに住んでおり，交差点 (w, h) の近くの会社に車で通っている．車は道路に沿ってのみ移動することができる．JOIさんは，通勤時間を短くするため，東または北にのみ向かって移動して通勤している．また，この都市では，交通事故を減らすために，次のような交通規則が設けられている：

• 交差点を曲がった車は，その直後の交差点で曲がることは出来ない．

すなわち，交差点で曲がったあとに1ブロックだけ進んで再び曲がることは許されない．このとき，JOIさんの通勤経路は何通り考えられるだろうか．

w と h が与えられたとき，JOIさんの通勤経路の個数を 100000 で割った余りを出力するプログラムを作成せよ．

入力

入力ファイルは1行からなり，空白を区切りとして2個の整数 w, h (2 ≦ w ≦ 100， 2 ≦ h ≦ 100) が書かれている． w は南北方向の道路の本数， h は東西方向の道路の本数を表す．

出力

出力は，JOIさんの通勤経路の個数を 100000 で割った余りだけを含む1行からなる．

入出力例

入力例1	入力例2
3 4	15 15	入力例1におけるJOIさんの通勤経路 ( 5 通り)
出力例1	出力例2
5	43688

入力例1において，JOIさんの通勤経路は図のように 5 通り考えられる．したがって，5を出力する．

入力例2において，JOIさんの通勤経路は 143688 通り考えられる．したがって，143688 を 100000 で割った余りである 43688 を出力する．

※各入出力例のデータは， 右クリック等によりファイルに保存して利用可能です．

採点用データ