Problem Description

A parenthesis sequence is a string consisting of ( and ). A valid parenthesis sequence is defined as follows:

• An empty string
• A valid parenthesis sequence $ A $ exists, and the string formed by concatenating ( , $ A $ , ) in this order
• Non-empty valid parenthesis sequences $ S, T $ exist, and the string formed by concatenating $ S $ , $ T $ in this order

Now, there are $ N $ distinguishable boxes.

You are thinking of putting a valid parenthesis sequence into each of the $ N $ boxes. However, you need to satisfy the following two conditions:

• The total number of ( in the $ N $ boxes is $ M $.
• No box should contain a parenthesis sequence of length $2 \times K$.

Find the number of ways to do this, modulo $ 998244353 $.

Two ways are considered different if there exists a box with a different parenthesis sequence in it.

Input Format

The input is given from the standard input in the following format:

$ N $ $ M $ $ K $

Output Format

Output the answer in one line.

Sample Input and Output

Sample Input #1

2 2 1

Sample Output #1

4

Sample Input #2

1 1 1

Sample Output #2

0

Sample Input #3

24 120 30

Sample Output #3

379268651

Notes/Hints

Constraints

• $1 \leq N \leq 10^6$
• $1 \leq M \leq 10^6$
• $1 \leq K \leq M$

Partial Points

• If you solve the dataset satisfying $1 \leq N, M \leq 2000$, you will be awarded $ 10 $ points.
• If you solve the dataset without additional constraints, you will be awarded an additional $ 490 $ points.

Sample Explanation 1

• (()), empty - ()(), empty - empty, (()) - empty, ()() for $ 4 $ ways.

见题面 Input 部分

见题面 Output 部分