← 返回题目列表

AtCoder · joi2010yo_e

E. 通勤路线

中文机器翻译题面 查看原题

配点: 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 输出该值。