UOJ Logo Universal Online Judge

UOJ

#144. 【UER #5】万圣节的糖果

统计

红包是一个慷慨大方的男孩子。今天是万圣节,红包正在家里分糖果。

这时候一群熊孩子们敲开了红包家的门,他们高呼着“不用给糖,只要捣蛋”的口号把红包刚分好的糖果又打乱了。这让红包很难过,于是他打算重新把这些糖果分好。

红包有 $n$ 个糖果, 编号为 $1$ 到 $n$,他打算把这些糖果分成 $m$ 堆来发给到他家要糖果的孩子们。

因为红包有轻微的强迫症,所以他想让分好的糖果满足如下的性质:

  1. 每一堆糖果的数目都大于 $0$。
  2. 每一个糖果都被分到恰好一堆糖果中。
  3. 对于每一堆糖果,把这些糖果按照标号排序之后,任意两个相邻的糖果的编号的奇偶性不同。例如 $\{ 1,3,4 \}$就是不满足这个条件的,$\{ 1,2,5,6,9 \}$就是满足这个条件的。

只分糖果实在是太无聊了,于是红包开始思考:究竟有多少种不同的分糖果的方案呢?

两个分糖果的方案是不同的当且仅当至少存在一个数对 $(i,j)$ 使得在第一个方案中第 $i$ 颗糖果在第 $j$ 堆中而第二个方案中不在。

输入格式

第一行两个正整数 $n,m$,保证 $n \geq m$。

输出格式

输出一个整数,表示满足红包要求的方案数。

答案可能很大,你只需要输出答案对 $998244353(7\times 17 \times 2^{23}+1$,一个质数$)$ 取模后的结果。

样例一

input

3 2

output

4

explanation

合法的方案有:

  1. $\{1\},\{2,3\}$
  2. $\{2,3\},\{1\}$
  3. $\{1,2\},\{3\}$
  4. $\{3\},\{1,2\}$

样例二

input

20 10

output

715672257

限制与约定

测试点编号$n, m$ 的规模
1$n \leq 20$,$m \leq 20$
2
3$n \leq 500$,$m \leq 500$
4
5
6$n \leq 1500$,$m \leq 1500$
7
8$n \leq 6000$,$m \leq 6000$
9
10

时间限制:$1\texttt{s}$

空间限制:$256\texttt{MB}$

下载

样例数据下载