Bối cảnh bài toán

Tôi thường hoài niệm về quá khứ...

Ba năm trước, Xiao Tangyuan vẫn là một cô bé học lớp 7 đáng yêu, khi đó cô ấy còn là bạn cùng lớp với Yuting-jiang...

Mô tả bài toán

Quay lại chủ đề chính, trong một buổi đọc sách toán học lớp 7, Xiao Tangyuan đã từng giải bài toán sau:

Chứng minh rằng với mọi dãy $a_0, a_1, a_2, a_3$ có độ dài $4$ chỉ chứa các giá trị $\pm 1$, ta có $4 \mid a_0a_1 + a_1a_2 + a_2a_3 + a_3a_0$.

Cô bé Xiao Tangyuan đáng yêu lúc đó đã giải quyết bài toán này trong chớp mắt, điều đó khiến cô ấy cảm thấy vô cùng hạnh phúc. Ba năm sau, khi đã nhiễm phải "sở thích xấu" về $\overset{\text{counting}}{\text{đếm}}$, cô ấy muốn nâng cấp bài toán này lên 🥰

Với một dãy $a_0 \dots a_{n-1}$ có độ dài $n$ chỉ chứa các giá trị $\pm 1$, ta định nghĩa hàm mưa của nó là: $$ S(a, m) = \displaystyle \sum_{k = 0}^{n - 1} \prod_{l = 0}^{m - 1} a_{(k + l) \bmod n} $$ Cho $n, m, k$, hãy tìm số lượng dãy $a$ trong $2^n$ dãy khác nhau sao cho hàm mưa $S(a, m) = k$. Kết quả cần được lấy dư theo $998\,244\,353$.

Dữ liệu vào

Bài toán này có nhiều bộ dữ liệu.

Dòng đầu tiên chứa một số nguyên dương $T$ là số lượng bộ dữ liệu.

$T$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $n, m, k$ tương ứng.

Dữ liệu ra

Gồm $T$ dòng, mỗi dòng chứa một số nguyên là kết quả của bộ dữ liệu tương ứng.

Ví dụ

Dữ liệu vào 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

Dữ liệu ra 1

12
256
108
10000
661235724
741150826
500003636
222931421
404094315

Ghi chú

Đối với bộ dữ liệu đầu tiên của ví dụ 1, các dãy không thỏa mãn là $a=[1,1,1,1]$, $a=[-1,-1,-1,-1]$, $a=[1,-1,1,-1]$ và $a=[-1,1,-1,1]$, vì vậy đáp án là $2^4-4=12$.

Đối với bộ dữ liệu thứ hai của ví dụ 1, các dãy thỏa mãn là những dãy có số lượng phần tử $-1$ là số lẻ, vì vậy đáp án là $2^8=256$.

Dữ liệu vào 2

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

Dữ liệu ra 2

176
1728
26160
368000
5413856
80212608

Dữ liệu vào 3

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

Dữ liệu ra 3

0
0
0
0

Nhiệm vụ con

Bài toán này áp dụng chấm điểm theo gói (bundled testing).

Với mọi dữ liệu, đảm bảo $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$.