#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 个街区而不能再次转弯。现在给定 wwhh,请编写一个程序来计算 JOI 先生的通勤路径有多少种可能。

要求将 JOI 先生的通勤路径个数除以 100,000100\\,000 的余数作为输出。

输入

输入只有一行,包含两个整数 w,hw, h (2leqqwleqq1002 \\leqq w \\leqq 1002leqqhleqq1002 \\leqq h \\leqq 100),以空格分隔。ww 表示南北方向的道路数目,hh 表示东西方向的道路数目。

输出

输出只有一行,包含 JOI 先生的通勤路径个数除以 100,000100\\,000 的余数。

输入例子 1

3 4

输出例子 1

5

2010-yo-t5-fig01.png

在输入例子 11 中,JOI 先生的通勤路径有 55 种可能。因此,输出结果为 55

输入例子 2

15 15

输出例子 2

43688

在输入例子 22 中,JOI 先生的通勤路径有 143,688143\\,688 种可能。因此,输出结果为 43,68843\\,688143,688143\\,688 除以 100,000100\\,000 的余数)。