7877 - 试题H：摆动序列 25’
时间限制 : 1 秒
内存限制 : 128 MB
如果一个序列的奇数项都比前一项大，偶数项都比前一项小，则称为一个摆动序列。
即 a_{2i} < a_{2i-1}, a_{2i+1} > a_{2i}。
小明想知道，长度为 m，每个数都是 1 到n 之间的正整数的摆动序列一共有多少个。
输入
输入一行包含两个整数 m，n。
输出
输出一个整数，表示答案。答案可能很大，请输出答案除以10000的余数。
样例
输入
3 4
输出
14
提示
样例说明
以下是符合要求的摆动序列：
2 1 2
2 1 3
2 1 4
3 1 2
3 1 3
3 1 4
3 2 3
3 2 4
4 1 2
4 1 3
4 1 4
4 2 3
4 2 4
4 3 4
评测用例规模与约定
对于 20\% 的评测用例，1 <= n, m <= 5；
对于 50\% 的评测用例，1 <= n, m <= 10；
对于 80\% 的评测用例，1 <= n, m <= 100；
对于所有评测用例，1 <= n, m <= 1000。
来源
2020年4月蓝桥杯官方B组省模拟赛