7877 - 试题H:摆动序列 25’

通过次数

94

提交次数

271

时间限制 : 1 秒
内存限制 : 128 MB

如果一个序列的奇数项都比前一项大,偶数项都比前一项小,则称为一个摆动序列。

a_{2i} < a_{2i-1}, a_{2i+1} > a_{2i}

小明想知道,长度为 m,每个数都是 1n 之间的正整数的摆动序列一共有多少个。

输入

输入一行包含两个整数 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组省模拟赛