題目背景

我常常追憶過去……

三年前的小糖原還是一隻萌萌可愛的初一小蘿莉，那時她還和雨停醬是同班同學呢……

題目描述

讓我們說回主題，小糖圓在初一數學讀書會上曾做過這樣一個題：

求證對於任意長為 $4$ 的僅包含 $\pm1$ 的序列 $a_0,a_1,a_2,a_3$，求證 $4\mid a_0a_1+a_1a_2+a_2a_3+a_3a_0$

可愛的小糖原當時一眼秒了這個題，使她感到十分幸福。三年後染上了$\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$ 中有多少個 $a$ 的雨函數值 $S(a,m)=k$，輸出數量對 $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

子任務

本題開啟捆綁測試。

對於所有數據，保證 $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$。