P9501 "RiOI-2" likely

Little E likes to arrange things in a circle rather than in a chain. Recently, she learned about plus and minus signs at school. She put them on the circle as a password. However, she has now forgotten it and only sees a number on the draft paper. What is it?

For a sequence $a_0 \dots a_{n-1}$ of length $n$ that contains only $\pm1$, define $S(a, m) = \displaystyle \sum_{k = 0}^{n - 1} \prod_{l = 0}^{m - 1} a_{(k + l) \bmod n}$. Given $n, m, k$, among the $2^n$ different sequences $a$, find how many different $a$ satisfy $S(a, m) = k$. Output the answer modulo $998,\!244,\!353$.

**This problem contains multiple test cases.** The first line contains a positive integer $T$, the number of test cases. The next $T$ lines each contain three integers, in order: $n, m, k$.

Output $T$ lines. Each line contains one integer, the answer for one test case.

### Sample Explanation For the first test case’s first dataset, the only sequences that do not satisfy the condition 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 test case’s second dataset, the only sequences that satisfy the condition are those where $a$ contains an odd number of $-1$, so the answer is $2^8 = 256$. ### Constraints and Notes **This problem uses bundled testdata.** | $\text{Subtask}$ | Score | $T \leq$ | $\sum n \leq$ | $m \leq$ | | :-: | :-: | :-: | :-: | :-: | | $0$ | $5$ | $1$ | $20$ | / | | $1$ | $10$ | $5$ | $10^5$ | $2$ | | $2$ | $10$ | $5$ | $10^5$ | $4$ | | $3$ | $15$ | / | $7\times10^3$ | / | | $4$ | $20$ | / | $10^5$ | / | | $5$ | $40$ | / | / | / | For all testdata, 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$, and $\sum n \leq 5\times10^6$. Translated by ChatGPT 5