011 - 通勤経路

時間制限 1 秒 / メモリ制限 64 MB / 得点 5 / x 0 /


TLE
1sec
MLE
64MB
得点
5

問題

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 を出力する.