P7820 [RC-05] 01 Sequence

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

**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$.

For each test case, output a non-negative integer, which is the number of possible sequences modulo $998244353$.

**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