题目描述

有一个长度为 $n$ 的 $01$ 序列，它的任意一个长为 $k$ 的连续子串中都有 $a$ 个 $0$ 或 $a+1$ 个 $0$。

求可能的序列数。答案很大，请输出其模 $998244353$ 的值。

输入格式

为了减小测试点个数，本题单个测试点内有多组数据。时间限制已经根据数据组数作了相应调整。

输入第一行是数据组数 $T$。

每组数据中，输入一行三个整数：$n,k,a$。

输出格式

对于每组数据，输出一个非负整数，为可能的序列数模 $998244353$ 的值。

3
4 3 1
5 3 1
15 7 2

10
16
1586

5
999999999 14 7
233333333 14 8
333333333 14 9
114514191 14 10
981011451 14 11

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$。

详细数据范围如下表：