Background

wkr is an OIer from the City of Magic, and he likes collecting black and white magic beads.

Problem Description

wkr wants to obtain a ring made by stringing together $n$ magic beads. However, he is not interested in ordinary rings, so he proposes the following requirements:

• wkr wants the ring to have exactly $m$ black magic beads and $n - m$ white magic beads.
• Since wkr believes black magic beads should not be too dense, he wants that on the ring there will not appear a consecutive segment of black magic beads whose length exceeds $k$.

In wkr’s mind, only rings that satisfy the above requirements are wonderful.

However, such rings may not be unique. wkr wants to know how many different rings satisfy his requirements. But wkr does not like doing calculations, so he hopes the smart you can tell him the answer.

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

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

Input Format

The input consists of $1$ line with $3$ non-negative integers $n, m, k$, whose meanings are described above. Adjacent numbers are separated by a single space.

Output Format

Output $1$ line with $1$ integer, representing the number of rings that meet the requirements.

6 3 2

3

17 8 6

1421

50000 20000 1

683811528

Hint

Explanation of Sample $1$

For rings made of $6$ magic beads, with exactly $3$ black magic beads and $3$ white magic beads, and with no consecutive segment of black magic beads of length greater than $2$, there are $3$ different rings, as shown below.

The ring shown below does not meet wkr’s requirements, because in this ring there exists a consecutive segment of black magic beads whose length exceeds $2$.

Subtasks

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

This problem uses bundled tests. There are $7$ subtasks, and the score and limits of each subtask are as follows:

• 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 restrictions.

Source

MtOI2018 迷途の家の水题大赛 T6

Problem setter: Imagine

72679

Translated by ChatGPT 5