Migrated from Lutece 2890 大鼻子情圣

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

我们这种人的口袋里，随时都有几封给梦中情人的信，我们的情人不过是随便借个名字，用幻想吹出来的肥皂泡，把信拿去吧，你可以使假戏成真。我本来是无病呻吟，漫无目的的吐露爱情，现在这些漂泊不定的鸟儿有地方栖息了，你可以从信里看出来。拿去吧，由于不是出自真心，话就说得格外动听，拿去吧，就这么办吧！ ——西哈诺 · 德 · 贝热拉克 《大鼻子情圣》

现在你有一个由 $n$ 个宝石组成的项链送给她，项链上宝石首尾相连成一个环，为了让这个项链更加美丽，你觉得对其做出一些限制：

• 其中恰好有 $m$ 个清石和 $n-m$ 个浊石。
• 项链不会有连续 $k$ 个相连的清石。

不过这样的项链可能不唯一，你想知道总共有多少项链满足限制，两个项链不同当且仅当一个项链不能仅通过旋转得到另一个项链。

Input

输入一行三个非负整数 $n,m,k$ 。

Output

输出一个整数表示答案对 $998244353$ 取模后的结果

Samples

4 2 1

1

6 3 2

3

17 14 11

34

Constraints

$1\le n\le 10^5,1\le k\le 10^5,0\le m\le 10^5,m\le n$。

Resources

2022 UESTC ICPC Training for Math and Geometry