문제 배경

나는 종종 과거를 추억하곤 한다……

3년 전의 샤오탕위안(小糖原)은 풋풋하고 귀여운 중학교 1학년 소녀였고, 그때는 위팅장(雨停酱)과 같은 반 친구였는데……

문제

본론으로 돌아가서, 샤오탕위안은 중1 수학 독서 모임에서 다음과 같은 문제를 푼 적이 있다:

길이가 $4$인 $\pm1$로만 구성된 임의의 수열 $a_0, a_1, a_2, a_3$에 대하여, $4 \mid a_0a_1+a_1a_2+a_2a_3+a_3a_0$임을 증명하시오.

귀여운 샤오탕위안은 당시 이 문제를 한눈에 풀어내어 매우 행복해했다. 3년 후, $\overset{\text{counting}}{\text{나쁜 취미}}$에 빠진 그녀는 이 문제를 강화하고 싶어 한다.🥰

길이가 $n$이고 $\pm1$로만 구성된 수열 $a_0 \dots a_{n-1}$에 대하여, 그 '비 함수(雨函数)'를 다음과 같이 정의한다: $$ S(a, m) = \displaystyle \sum_{k = 0}^{n - 1} \prod_{l = 0}^{m - 1} a_{(k + l) \bmod n} $$ $n, m, k$가 주어질 때, $2^n$개의 서로 다른 $a$ 중에서 비 함수 값 $S(a, m)=k$를 만족하는 $a$의 개수를 구하고, 그 결과를 $998,244,353$으로 나눈 나머지를 출력하시오.

입력

이 문제는 여러 개의 테스트 케이스로 구성된다.

첫 번째 줄에 테스트 케이스의 개수를 나타내는 정수 $T$가 주어진다.

이어지는 $T$개의 줄에는 각각 세 정수 $n, m, k$가 순서대로 주어진다.

출력

총 $T$개의 줄에 걸쳐, 각 테스트 케이스에 대한 정답을 출력한다.

예제

예제 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

예제 1 출력

12
256
108
10000
661235724
741150826
500003636
222931421
404094315

참고 1

첫 번째 예제의 첫 번째 데이터에서 조건을 만족하지 않는 경우는 $a=[1,1,1,1]$, $a=[-1,-1,-1,-1]$, $a=[1,-1,1,-1]$, $a=[-1,1,-1,1]$뿐이므로, 정답은 $2^4-4=12$이다.

첫 번째 예제의 두 번째 데이터에서 조건을 만족하는 경우는 $a$에 $-1$이 홀수 개 포함된 경우뿐이므로, 정답은 $2^8=256$이다.

예제 2 입력

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

예제 2 출력

176
1728
26160
368000
5413856
80212608

예제 3 입력

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

예제 3 출력

0
0
0
0

서브태스크

이 문제는 번들 테스트(bundled test)를 시행한다.

모든 데이터에 대하여 $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\times10^6$임이 보장된다.