[MtOI2018]魔力环

题目背景

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

题目描述

Shone 希望能够得到一个由 $n$ 个魔力珠串成的环。不过他对普通的环并不感兴趣,因此他提出了如下的要求: - Shone 希望在这个环上,**恰好**有 $m$ 个黑色的魔力珠与 $n - m$ 个白色的魔力珠。 - 由于 Shone 认为黑色魔力珠不应过于密集,因此 Shone 希望这个环上**不会**出现一段**连续**的黑色魔力珠,其长度**超过** $k$。 在 Shone 的心目中,满足上述要求的环才是美妙的。 不过这样的环可能并不唯一。 Shone 想要知道共有多少种不同的环满足他所提出的要求。然而 Shone 并不喜欢计算,他希望聪明的你能够告诉他答案。 在这里,我们认为**两个环是不同的,当且仅当其中一个环仅通过旋转无法得到另一个环**。 由于答案可能过大,因此输出答案对 $998, 244, 353$ 取模后的结果。

输入输出格式

输入格式


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

输出格式


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

输入输出样例

输入样例 #1

6 3 2

输出样例 #1

3

输入样例 #2

17 8 6

输出样例 #2

1421

输入样例 #3

50000 20000 1

输出样例 #3

683811528

说明

#### 样例解释 $1$ 由 $6$ 个魔力珠串成,满足其中恰好有 $3$ 个黑色魔力珠与 $3$ 个白色魔力珠,且不存在长度超过 $2$ 的连续的黑色魔力珠的不同的环共有 $3$ 种,如下图所示。 ![QQ20181002002120.png](https://www.z4a.net/images/2018/10/02/QQ20181002002120.png) 下图所示的环不满足 Shone 提出的要求,因为在这个环中,存在一段连续的黑色魔力珠,长度超过了 $2$。 ![QQ20181002002148.png](https://www.z4a.net/images/2018/10/02/QQ20181002002148.png) ### 子任务 所有测试点均满足 $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 迷途の家の水题大赛](https://www.luogu.org/contest/11260) T6 出题人:Imagine 72679