[RC-05] 01 序列
题目描述
有一个长度为 $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<k$。
详细数据范围如下表：
| 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$ | $\le 8$ | 无 | $12$ |
| $6$ | $\le 10^9$ | $\le 9$ | 无 | $12$ |
| $7$ | $\le 10^9$ | $\le 11$ | 无 | $12$ |
| $8$ | $\le 10^9$ | $\le 12$ | 无 | $12$ |
| $9$ | $\le 10^9$ | $\le 13$ | 无 | $12$ |
| $10$ | $\le 10^9$ | $\le 14$ | 无 | $12$ |