Problem Description

There is a $01$ sequence of length $n$. In any consecutive substring of length $k$, there are either $a$ zeros or $a+1$ zeros.

Find the number of possible sequences. The answer can be very large, so output it modulo $998244353$.

Input Format

To reduce the number of test points, this problem contains multiple test cases within a single test point. The time limit has been adjusted accordingly based on the number of test cases.

The first line contains the number of test cases $T$.

For each test case, one line contains three integers: $n, k, a$.

Output Format

For each test case, output a non-negative integer, which is the number of possible sequences modulo $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

Hint

This problem uses bundled judging.

For all data, $1\le T\le 5$, $1\le k\le n\le 10^9$, $1\le k\le 14$, $0\le a<k$.

The detailed Constraints are shown in the table below:

Translated by ChatGPT 5