配点: 100 点
問題
JOI 先生居住的加拿大某个城市,由南北方向笔直延伸的 w 条道路和东西方向笔直延伸的 h 条道路构成棋盘格状的区划。
南北方向的 w 条道路,从西向东依次编号为 1, 2, \ldots, w 。另外,东西方向的 h 条道路,从南向北依次编号为 1, 2, \ldots, h 。从西数第 i 条南北向道路与从南数第 j 条东西向道路的交叉点表示为 (i, j)。
JOI 先生住在交叉点 (1, 1) 附近,交叉点 (w, h) 附近的公司开车上下班。汽车只能沿着道路移动。为了缩短通勤时间,JOI先生在通勤时只向东或向北移动。此外,为了减少这座城市的交通事故,制定了以下规则:
- 在交叉路口转弯的车辆,不能在紧接着的交叉路口再次转弯。
换句话说,在交叉路口转弯后 1 不允许只移动一个街区就再次转弯。在这种情况下,JOI先生的通勤路线有多少种可能呢?
w 和 h 给定时,求JOI先生通勤路线的数量。 100\,000 的余数。 从
入力
输入为 1 行开始,以空格分隔 2 个整数 w, h (2 \leqq w \leqq 100,2 \leqq h \leqq 100) 被写下。w 是南北方向道路的数量,h 表示东西方向道路的数量。
出力
输出是 JOI 先生通勤路线的数量 100\,000 除以后取余数的结果 1 行。
入力例 1
3 4
出力例 1
5

入力例 1 中,JOI 先生的通勤路线如图所示 5 种考虑方式。因此,5 输出该值。
入力例 2
15 15
出力例 2
43688
入力例 2 中,JOI 先生的通勤路线是 143\,688 种考虑方式。因此,143\,688 是 100\,000 除以后的余数是 43\,688 输出该值。