4383. [郑轻校赛 2026] 合理分配

Problem H. 合理分配

在 ACM 赛制中，解题数目优先，但有时不得不为题目设置分值。小王负责给一场比赛出题，共有 $n$ 道题目，题目难度从低到高依次编号为 $1,2,\dots,n$。他需要为每道题设定一个整数分数 $A_i$，满足以下条件：

• 分数范围：$1 \le A_i \le m$。
• 难度高的题目分数不低于难度低的题目，即 $A_1 \le A_2 \le \cdots \le A_n$。
• 做题数多的总分一定严格大于做题数少的总分。

形式化讲：任意两个不同的非空子集 $S,T \subseteq \{1,2,\dots,n\}$，若 $|S| > |T|$，则：

小王想知道有多少种不同的分数分配方案满足上述条件。请输出方案数对 $998244353$ 取模的结果。

Input

一行两个整数 $n,m$ $(2 \le n,m \le 5000)$。

Output

输出一个整数，表示方案数对 $998244353$ 取模后的结果。

Example

样例输入1

2 2

样例输出1

3

样例输入2

3 3

样例输出2

7

样例输入3

5 2

样例输出3

3

样例输入4

100 100

样例输出4

96354127

Note

样例1：合法方案为 $(1,1)$、$(1,2)$、$(2,2)$。

样例2：合法方案包括 $(1,1,1)$、$(1,2,2)$、$(1,3,3)$、$(2,2,2)$、$(2,2,3)$、$(2,3,3)$、$(3,3,3)$。

$(1,1,2)$、$(1,2,3)$ 不合法，因为存在不同大小集合总分相同的情况。$(1,1,3)$ 不合法，因为较多题目的总分反而更小。

来源

郑州轻工业大学“筑梯杯”第十八届程序设计大赛暨省内高校邀请赛 H

数据来源：qiuyu