1 测测你的FFT（fft）

1.1 题目描述

给定 $n, m, k$，考虑所有长为 $n$ 的 01 串，满足任意连续 $m$ 个字符都有至少 $k$ 个 1。

定义一个串的权值为这个串中 $1$ 的个数，记 $X$ 为所有满足条件的串中权值最小的权值，

求有多少满足条件的串权值等于 $X$。

1.2 输入格式

第一行一个数 $T$，表示数据组数。

对于每组数据，一行三个数 $n, m, k$。

1.3 输出格式

T 行每行一个非负整数，表示串的个数 $\text{mod} 998244353$ 的结果。

1.4 样例输入

4
2 2 1
4 2 1
50 10 3
100000000 1000000 100000

1.5 样例输出

2
3
16195608
222752520

1.6 样例解释

第一组数据，满足条件的串有 $01,10,11$。 其中 $01,10$ 的权值为 $1$，$11$ 的权值为 $2$。 因此最小值是 $1$，个数是 $2$，只需输出 $2$。