题目描述
有一个长度为 $n$ 的 $01$ 序列，它的任意一个长为 $k$ 的连续子串中都有 $a$ 个 $0$ 或 $a+1$ 个 $0$。
求可能的序列数。答案很大，请输出其模 $998244353$ 的值。
输入格式
为了减小测试点个数，本题单个测试点内有多组数据。时间限制已经根据数据组数作了相应调整。
输入第一行是数据组数 $T$。
每组数据中，输入一行三个整数：$n,k,a$。
输出格式
对于每组数据，输出一个非负整数，为可能的序列数模 $998244353$ 的值。
样例
样例输入 1
3 4 3 1 5 3 1 15 7 2
样例输出 1
10 16 1586
样例输入 2
5 999999999 14 7 233333333 14 8 333333333 14 9 114514191 14 10 981011451 14 11
样例输出 2
278944053 533032251 736989868 589364996 572821890
数据范围与提示
本题捆绑测试。
对于所有数据，$1\le T\le 5$，$1\le k\le n\le 10^9$，$1\le k\le 14$，$0\le a\le k-1$。
详细数据范围如下表：
| Subtask 编号 | $n$ | $k$ | 特殊性质 | 分数 |
|---|---|---|---|---|
| $1$ | $\le 18$ | $\le 14$ | 无 | $1$ |
| $2$ | $\le 2000$ | $\le 10$ | 无 | $8$ |
| $3$ | $\le 10^9$ | $\le 14$ | $a=0$ | $7$ |
| $4$ | $\le 10^9$ | $\le 7$ | 无 | $12$ |
| $5$ | $\le 10^9$ | $=8$ | 无 | $12$ |
| $6$ | $\le 10^9$ | $=9$ | 无 | $12$ |
| $7$ | $\le 10^9$ | $=11$ | 无 | $12$ |
| $8$ | $\le 10^9$ | $=12$ | 无 | $12$ |
| $9$ | $\le 10^9$ | $=13$ | 无 | $12$ |
| $10$ | $\le 10^9$ | $=14$ | 无 | $12$ |