P15612 [ICPC 2021 Jakarta R] Feeder Robot

文森特将他的退休计划从养马和养羊改为养鸡。他采购了 $N$ 只鸡，并将每只鸡放入它们自己的鸡舍中。鸡舍被放置在一条直线上，从左到右依次编号为 $1$ 到 $N$。 为了让他的退休生活幸福（至少他是这么想的），文森特买了一个喂食机器人。这个机器人装载着 $M$ 颗饲料颗粒，并将它们分发给鸡群。喂食机器人会从一个鸡舍移动到相邻的鸡舍，并向它访问的每个鸡舍分发 $1$ 颗饲料。如果一个鸡舍被机器人访问了 $x$ 次（包括机器人的初始位置），那么它将获得 $x$ 颗饲料。 然而，文森特刚刚注意到他无法控制机器人的移动方式。设机器人位于鸡舍 $p$ 前。如果机器人还有剩余饲料要分发，它会随机移动到相邻的鸡舍（鸡舍 $p - 1$ 或 $p + 1$），并向那个鸡舍分发 $1$ 颗饲料。重复此过程，直到机器人没有饲料可分发。注意，如果 $p = 1$，则机器人将移动到鸡舍 $2$；类似地，如果 $p = N$，则机器人将移动到鸡舍 $N - 1$。 尽管你是他唯一的朋友，但文森特还是不喜欢你，于是他向你发起挑战。挑战是：如果机器人从鸡舍 $A$ 出发，计算有多少种可能的饲料分布。一个饲料分布被定义为一个元组 $\langle R, S_{1..N}\rangle$，其中 $R$ 是机器人的最终位置，$S_{i}$ 是鸡舍 $i$ 获得的饲料颗粒数。两个分布被认为是不同的当且仅当机器人的最终位置不同，或者存在某个鸡舍获得的饲料数量不同。机器人的移动路径或鸡舍获得饲料的顺序无关紧要。 由于输出可能非常大，文森特要求你给出输出除以 $998\,244\,353$ 后的非负余数。他相信你无法解决这个问题，因此同意如果你成功应对挑战，将给予你丰厚的奖励。 例如，设 $N = 4$，$M = 3$，$A = 2$。此例中有 $3$ 种不同的饲料分布。 - $\langle 2, \{1, 2, 0, 0\}\rangle$：机器人结束于鸡舍 $2$，每个鸡舍获得的饲料数量为 $\{1, 2, 0, 0\}$。导致此分布的机器人移动路径为：机器人从鸡舍 $2$ 开始，向鸡舍 $2$ 分发 $1$ 颗饲料；然后移动到鸡舍 $1$，向鸡舍 $1$ 分发 $1$ 颗饲料；然后移动到鸡舍 $2$，向鸡舍 $2$ 分发 $1$ 颗饲料。简记为 $2 \rightarrow 1 \rightarrow 2$。 - $\langle 2, \{0, 2, 1, 0\}\rangle$：机器人结束于鸡舍 $2$，每个鸡舍获得的饲料数量为 $\{0, 2, 1, 0\}$。机器人的移动路径为 $2 \rightarrow 3 \rightarrow 2$。 - $\langle 4, \{0, 1, 1, 1\}\rangle$：机器人结束于鸡舍 $4$，每个鸡舍获得的饲料数量为 $\{0, 1, 1, 1\}$。机器人的移动路径为 $2 \rightarrow 3 \rightarrow 4$。

输入包含三个整数 $N$、$M$ 和 $A$（$2 \leq N \leq 100\,000$；$1 \leq M \leq 200\,000$；$1 \leq A \leq N$），分别表示鸡舍的数量、饲料颗粒的数量以及喂食机器人的起始位置。

输出一行一个整数，表示不同饲料分布的数量除以 $998\,244\,353$ 后的非负余数。

#### 样例输入/输出 #2 解释 此例中有 $3$ 种不同的饲料分布。 - $\langle 2, \{2, 3, 0\}\rangle$：机器人结束于鸡舍 $2$，每个鸡舍获得的饲料数量为 $\{2, 3, 0\}$。机器人的移动路径为 $2 \rightarrow 1 \rightarrow 2 \rightarrow 1 \rightarrow 2$。 - $\langle 2, \{0, 3, 2\}\rangle$：机器人结束于鸡舍 $2$，每个鸡舍获得的饲料数量为 $\{0, 3, 2\}$。机器人的移动路径为 $2 \rightarrow 3 \rightarrow 2 \rightarrow 3 \rightarrow 2$。 - $\langle 2, \{1, 3, 1\}\rangle$：机器人结束于鸡舍 $2$，每个鸡舍获得的饲料数量为 $\{1, 3, 1\}$。机器人的移动路径为 $2 \rightarrow 1 \rightarrow 2 \rightarrow 3 \rightarrow 2$ 或 $2 \rightarrow 3 \rightarrow 2 \rightarrow 1 \rightarrow 2$；两者给出相同的分布，即机器人最终位于同一鸡舍，且每个鸡舍获得的饲料数量相同。 #### 样例输入/输出 #3 解释 此例中有 $6$ 种不同的饲料分布：$\langle 1, \{3, 3, 0\}\rangle$、$\langle 1, \{2, 3, 1\}\rangle$、$\langle 3, \{2, 3, 1\}\rangle$、$\langle 1, \{1, 3, 2\}\rangle$、$\langle 3, \{1, 3, 2\}\rangle$ 和 $\langle 3, \{0, 3, 3\}\rangle$。 翻译由 DeepSeek 完成