Problem Background

wkr is an OIer from the Magic Capital, who enjoys collecting black and white magic beads.

Problem Description

wkr wishes to obtain a circle made up of $n$ magic beads. However, he is not interested in ordinary circles, so he has the following requirements:

• wkr wants exactly $m$ black magic beads and $n - m$ white magic beads in this circle.
• Since wkr believes that black magic beads should not be too densely packed, he wants the circle to not have any continuous segments of black magic beads that are longer than $k$.

In wkr's mind, only circles that meet these requirements are beautiful.

However, such circles may not be unique. wkr wants to know how many different circles satisfy his requirements. Since wkr dislikes calculations, he hopes that you, a clever person, can tell him the answer.

Here, we consider two circles to be different if and only if one circle cannot be obtained from the other by rotation alone.

Since the answer may be very large, output the result modulo $998,244,353$.

Input Format

The input consists of a single line with three non-negative integers $n, m, k$, as described in the problem statement, separated by single spaces.

Output Format

The output consists of a single line with one integer, representing the number of circles that meet the requirements.

Sample Input and Output

Sample Input #1

6 3 2

Sample Output #1

3

Sample Input #2

17 8 6

Sample Output #2

1421

Sample Input #3

50000 20000 1

Sample Output #3

683811528

Notes

Sample 1 Explanation

There are 3 different circles made up of 6 magic beads, with exactly 3 black and 3 white beads, and no continuous segments of black beads longer than 2, as shown below.

The circle shown below does not meet wkr's requirements because it contains a continuous segment of black beads longer than 2.

Subtasks

All test cases satisfy $1 \leq n, k \leq 10^5, 0 \leq m \leq 10^5$ and $m \leq n$.

This problem is bundled with subtasks, with a total of 7 subtasks, each with its own score and constraints:

• Subtask 1 (3 points): $m = 0$
• Subtask 2 (5 points): $n \leq 4$
• Subtask 3 (8 points): $n \leq 18$
• Subtask 4 (7 points): $m = 2$
• Subtask 5 (19 points): $k = 1$
• Subtask 6 (27 points): $\gcd(n,m) \leq 2$
• Subtask 7 (31 points): No special constraints

Problem Source

MtOI2018 Lost Home's Water Problem Contest T6

Problem Author: Imagine

72679

见题面 Input 部分

见题面 Output 部分