시간 제한메모리 제한제출정답맞은 사람정답 비율
2 초 512 MB0000.000%

문제

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$.

예제 입력 1

2 2 1

예제 출력 1

4

예제 입력 2

1 1 1

예제 출력 2

0

예제 입력 3

24 120 30

예제 출력 3

379268651

힌트

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

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

So, the answer is $4$.