P15612 [ICPC 2021 Jakarta R] Feeder Robot

Vincent switches his retirement plan from raising horses and goats into raising chickens. He procures $N$ chickens and lays each of them into their own coop (hen house). The coops are placed on a single line numbered sequentially from $1$ at the left-most to $N$ at the right-most. To make his retirement blissful (or at least he thought), Vincent buys a feeder robot. This feeder robot is to be loaded with $M$ pellets and it will distribute them for the chickens to feed on. The feeder robot will move from one coop to an adjacent coop and distribute $1$ pellet to each coop it visits. If a coop is visited $x$ times by the robot including the robot's initial position, then it will get $x$ pellets. However, Vincent has just noticed that he cannot control how the robot moves. Let the robot be in front of coop $p$. If the robot still has pellets to distribute, it will move to an adjacent coop (coop $p - 1$ or $p + 1$) at random and distributes $1$ pellet to that coop. This process repeats until the robot has no more pellets to distribute. Note that if $p = 1$, then the robot will move to coop $2$; similarly, if $p = N$, then the robot will move to coop $N - 1$. Since Vincent dislikes you even though you are his only friend, he challenges you to a problem. The challenge is to count how many possible pellets distributions are there if the robot starts at coop $A$. A pellets distribution is defined as a tuple $\langle R, S_{1..N}\rangle$ where $R$ is the final position of the robot and $S_{i}$ is the number of pellets coop $i$ gets. Two distributions are different if and only if the final position of the robot differs or there is a coop that gets a different number of pellets. The robot's movement or the order when the coop gets a pellet does not matter. Since the output can be quite big, Vincent requires you to give him the non-negative remainder when the output is divided by $998 244 353$. Believing that you cannot solve it, Vincent agrees to award you with a hefty reward if you managed to solve his challenge. For example, let $N = 4$, $M = 3$, and $A = 2$. In this example, there are $3$ different pellets distributions. - $\langle 2, \{1, 2, 0, 0\}\rangle$: The robot ends at coop $2$ and the number of pellets each coop gets is $\{1, 2, 0, 0\}$. The robot's movement that causes this distribution is: The robot starts at coop $2$ and distributes $1$ pellet to coop $2$; it moves to coop $1$ and distributes $1$ pellet to coop $1$; it moves to coop $2$ and distributes $1$ pellet to coop $2$. In a simple notation, the robot's movement is $2 \rightarrow 1 \rightarrow 2$ - $\langle 2, \{0, 2, 1, 0\}\rangle$: The robot ends at coop $2$ and the number of pellets each coop gets is $\{0, 2, 1, 0\}$. The robot's movement is $2 \rightarrow 3 \rightarrow 2$. - $\langle 4, \{0, 1, 1, 1\}\rangle$: The robot ends at coop $4$ and the number of pellets each coop gets is $\{0, 1, 1, 1\}$. The robot's movement is $2 \rightarrow 3 \rightarrow 4$.

Input contains three integers $N$ $M$ $A$ ($2 \leq N \leq 100 000$; $1 \leq M \leq 200 000$; $1 \leq A \leq N$) representing the number of coops, the number of pellets, and the starting position of the feeder robot, respectively.

Output contains an integer in a line representing the non-negative remainder when the number of different pellets distributions is divided by $998 244 353$.

#### Explanation for the sample input/output #2 There are $3$ different pellets distributions in this case. - $\langle 2, \{2, 3, 0\}\rangle$: The robot ends at coop $2$ and the number of pellets each coop gets is $\{2, 3, 0\}$. The robot's movement is $2 \rightarrow 1 \rightarrow 2 \rightarrow 1 \rightarrow 2$. - $\langle 2, \{0, 3, 2\}\rangle$: The robot ends at coop $2$ and the number of pellets each coop gets is $\{0, 3, 2\}$. The robot's movement is $2 \rightarrow 3 \rightarrow 2 \rightarrow 3 \rightarrow 2$. - $\langle 2, \{1, 3, 1\}\rangle$: The robot ends at coop $2$ and the number of pellets each coop gets is $\{1, 3, 1\}$. The robot's movement is $2 \rightarrow 1 \rightarrow 2 \rightarrow 3 \rightarrow 2$ or $2 \rightarrow 3 \rightarrow 2 \rightarrow 1 \rightarrow 2$; both of them give the same distribution, i.e. the robot ends at the same coop and each coop gets the same number of pellets in both distributions. #### Explanation for the sample input/output #3 There are $6$ different pellets distributions in this case: $\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$, and $\langle 3, \{0, 3, 3\}\rangle$.