#joi2010yoe. [joi2010yo_e]通勤経路
[joi2010yo_e]通勤経路
问题
JOI 先生生活在加拿大的一个城市,这个城市的道路被分割成了格子状,其中有 条南北方向的道路和 条东西方向的道路。
南北方向的 条道路从西到东依次编号为 。东西方向的 条道路从南到北依次编号为 。第 条南北方向的道路和第 条东西方向的道路的交叉点用 () 表示。
JOI 先生住在交叉点 () 附近,并且通过交叉点 附近的一家公司通勤。车辆只能沿着道路移动。为了缩短通勤时间,JOI 先生只会向东或者向北移动通勤。另外,为了减少交通事故,在这座城市中有一些交通规则:
- 转弯的车辆不能在紧接着的交叉点再次转弯。
也就是说,在转弯之后只能前进 个街区而不能再次转弯。现在给定 和 ,请编写一个程序来计算 JOI 先生的通勤路径有多少种可能。
要求将 JOI 先生的通勤路径个数除以 的余数作为输出。
输入
输入只有一行,包含两个整数 (,),以空格分隔。 表示南北方向的道路数目, 表示东西方向的道路数目。
输出
输出只有一行,包含 JOI 先生的通勤路径个数除以 的余数。
输入例子 1
3 4
输出例子 1
5
在输入例子 中,JOI 先生的通勤路径有 种可能。因此,输出结果为 。
输入例子 2
15 15
输出例子 2
43688
在输入例子 中,JOI 先生的通勤路径有 种可能。因此,输出结果为 ( 除以 的余数)。