Problem Background

Little E enjoys arranging things in a circular manner rather than a linear chain.

Recently, she learned about positive and negative signs at school. She placed them in a circle as a password.

However, she has now forgotten them, and all she sees is a number on her draft paper. What is it?

Problem Description

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

Given \( n, m, k \), find out how many different sequences \( a \) out of \( 2^n \) satisfy \( S(a, m) = k \).

The answer should be taken modulo \( 998,244,353 \).

Input Format

This problem contains multiple test cases.

The first line contains a positive integer \( T \) representing the number of test cases.

The next \( T \) lines each contain three integers \( n, m, k \) in that order.

Output Format

Output \( T \) lines, each containing an integer representing the answer for that test case.

Sample Input and Output

Sample Input #1

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

Sample Output #1

12
256
108
10000
661235724
741150826
500003636
222931421
404094315

Sample Input #2

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

Sample Output #2

176
1728
26160
368000
5413856
80212608

Sample Input #3

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

Sample Output #3

0
0
0
0

Notes

Sample Explanation

For the first sample's first case, the only sequences that do not meet the requirement 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 sample's second case, the only sequences that meet the requirement are those with an odd number of \(-1\)'s, so the answer is \( 2^8 = 256 \).

Data Constraints and Assumptions

This problem is bundled with other tasks.

For all data, 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 \), \( \sum n \leq 5 \times 10^6 \).

见题面 Input 部分

见题面 Output 部分