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