23115번 - Multiple Parentheses 다국어

Consider strings consisting of the brackets '(' and ')'. 

The regular bracket sequences are the strings which can be obtained by the following rules:

• Empty string is a regular bracket sequence.
• If $A$ is a regular bracket sequence, then ($A$) is a regular bracket sequence.
• If $A$ and $B$ are regular bracket sequences, then the concatenation of $A$ and $B$ is a regular bracket sequence.

You are given $N$ boxes numbered $1, 2, \ldots, N$, and also two integers, $M$ and $K$. Your task is to put exactly one regular bracket sequence in each of $N$ boxes such that the following conditions are met:

• The total number of '(' brackets in all $N$ boxes is equal to $M$.
• The regular bracket sequences of length $2 \cdot K$ cannot be put into the boxes.

Count the number of different ways to do that. Two distributions are considered different if there exists a number $i$ such that box $i$ contains different regular bracket sequences in those distributions.

Because the answer may be very large, print the answer modulo $998\,244\,353$.

The input contains one line with three integers $N$, $M$, and $K$ in it ($1 \le M, N \le 10^6$, $1 \le K \le M$).

Print the answer modulo $998\,244\,353$.

For the first example, the following distributions meet the conditions:

• (()), empty;
• ()(), empty;
• empty, (());
• empty, ()().

So, the answer is $4$.