Background

Little E likes to arrange things in a circle rather than in a chain.

Recently, she learned about plus and minus signs at school. She put them on the circle as a password.

However, she has now forgotten it and only sees a number on the draft paper. What is it?

Problem Description

For a sequence $a_0 \dots a_{n-1}$ of length $n$ that contains only $\pm1$, define $S(a, m) = \displaystyle \sum_{k = 0}^{n - 1} \prod_{l = 0}^{m - 1} a_{(k + l) \bmod n}$.

Given $n, m, k$, among the $2^n$ different sequences $a$, find how many different $a$ satisfy $S(a, m) = k$.

Output the answer modulo $998,\!244,\!353$.

Input Format

This problem contains multiple test cases.

The first line contains a positive integer $T$, the number of test cases.

The next $T$ lines each contain three integers, in order: $n, m, k$.

Output Format

Output $T$ lines. Each line contains one integer, the answer for one test case.

9
4 2 0
9 9 -9
9 3 3
20 8 -12
114 5 14
191 9 81
1036 854 104
998244 353 4
2147483 64 7

12
256
108
10000
661235724
741150826
500003636
222931421
404094315

6
8 4 0
12 4 0
16 4 0
20 4 0
24 4 0
28 4 0

176
1728
26160
368000
5413856
80212608

4
6 2 0
10 2 0
9 9 7
9 3 6

0
0
0
0

Hint

Sample Explanation

For the first test case’s first dataset, the only sequences that do not satisfy the condition are $a = [1, 1, 1, 1]$, $a = [-1, -1, -1, -1]$, $a = [1, -1, 1, -1]$, and $a = [-1, 1, -1, 1]$, so the answer is $2^4 - 4 = 12$.

For the first test case’s second dataset, the only sequences that satisfy the condition are those where $a$ contains an odd number of $-1$, so the answer is $2^8 = 256$.

Constraints and Notes

This problem uses bundled testdata.

For all testdata, it is guaranteed that $2 \leq m \leq n \leq 5\times 10^6$, $0 \leq \lvert k\rvert \leq n$, $1 \leq T \leq 10$, and $\sum n \leq 5\times10^6$.

Translated by ChatGPT 5