背景

私はよく過去を振り返ります……

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$ となるものの個数を求めてください。結果は $998,244,353$ で割った余りを出力してください。

入力

この問題には複数のテストケースが含まれます。

1行目に、テストケースの数を示す正整数 $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つ目のサンプルケースの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$ となります。

1つ目のサンプルケースの2つ目のデータについて、条件を満たすのは $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$ を満たします。