题目背景

wkr 是一名来自魔力之都的 OIer，他喜欢收集黑色与白色的魔力珠。

题目描述

wkr 希望能够得到一个由 $n$ 个魔力珠串成的环。不过他对普通的环并不感兴趣，因此他提出了如下的要求：

• wkr 希望在这个环上，恰好有 $m$ 个黑色的魔力珠与 $n - m$ 个白色的魔力珠。
• 由于 wkr 认为黑色魔力珠不应过于密集，因此 wkr 希望这个环上不会出现一段连续的黑色魔力珠，其长度超过 $k$。

在 wkr 的心目中，满足上述要求的环才是美妙的。

不过这样的环可能并不唯一。 wkr 想要知道共有多少种不同的环满足他所提出的要求。然而 wkr 并不喜欢计算，他希望聪明的你能够告诉他答案。

在这里，我们认为两个环是不同的，当且仅当其中一个环仅通过旋转无法得到另一个环。

由于答案可能过大，因此输出答案对 $998, 244, 353$ 取模后的结果。

输入格式

输入共 $1$ 行 $3$ 个非负整数 $n, m, k$，其意义见题目描述，相邻的两个数用单个空格隔开。

输出格式

输出共 $1$ 行 $1$ 个整数，表示满足要求的环的数量。

6 3 2

3

17 8 6

1421

50000 20000 1

683811528

提示

样例 $1$ 解释

由 $6$ 个魔力珠串成，满足其中恰好有 $3$ 个黑色魔力珠与 $3$ 个白色魔力珠，且不存在长度超过 $2$ 的连续的黑色魔力珠的不同的环共有 $3$ 种，如下图所示。

下图所示的环不满足 wkr 提出的要求，因为在这个环中，存在一段连续的黑色魔力珠，长度超过了 $2$。

子任务

所有测试点均满足 $1 \leq n, k \leq 10^5, 0 \leq m \leq 10^5$ 且 $m \leq n$。

本题采用捆绑测试，共有 $7$ 个子任务，各子任务的分值和限制如下：

• 子任务 1（3 分）：$m = 0$
• 子任务 2（5 分）：$n \leq 4$
• 子任务 3（8 分）：$n \leq 18$
• 子任务 4（7 分）：$m = 2$
• 子任务 5（19 分）：$k = 1$
• 子任务 6（27 分）：$\gcd(n,m) \leq 2$
• 子任务 7（31 分）：无特殊限制

题目来源

MtOI2018 迷途の家の水题大赛 T6

出题人：Imagine

72679