#joi2010yoe. [joi2010yo_e]通勤経路

[joi2010yo_e]通勤経路

問題

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

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

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

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

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

wwhh が与えられたとき,JOI さんの通勤経路の個数を 100,000100\\,000 で割った余りを出力するプログラムを作成せよ.


入力

入力は 11 行からなり,空白を区切りとして 22 個の整数 w,hw, h (2leqqwleqq1002 \\leqq w \\leqq 1002leqqhleqq1002 \\leqq h \\leqq 100) が書かれている.ww は南北方向の道路の本数,hh は東西方向の道路の本数を表す.

出力

出力は,JOI さんの通勤経路の個数を 100,000100\\,000 で割った余りだけを含む 11 行からなる.


入力例 1

3 4

出力例 1

5

2010-yo-t5-fig01.png

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


入力例 2

15 15

出力例 2

43688

入力例 22 において,JOIさんの通勤経路は 143,688143\\,688 通り考えられる.したがって,143,688143\\,688100,000100\\,000 で割った余りである 43,68843\\,688 を出力する.