Problem Description

Xiao Lan needs to arrange a duty schedule for teaching assistants (TAs) of a course. The schedule lasts for $n$ days, and there are $m$ TAs, numbered from $1$ to $m$.

Each day, you may assign any number of TAs to be on duty. The entire schedule must satisfy the following requirements:

• Each TA must be on duty at least once.
• For easier handover, if a TA is on duty on day $i$, then they must also be on duty on day $i - 1$ or day $i + 1$.
• To avoid excessive fatigue, the same TA cannot be on duty for $3$ consecutive days.

The total workload of a schedule is defined as the sum of the duty days of all TAs. That is, if the $i$-th TA is on duty for a total of $c_i$ days, then the total workload is:

$$\begin{aligned} c_1 + c_2 + \dots + c_m \end{aligned}$$

Now the total workload is required to be exactly $K$. Please compute how many duty schedules satisfy the requirements. Since the answer may be very large, you only need to output the result modulo $998244353$.

Input Format

The first line contains a positive integer $T$, representing the number of queries.

The next $T$ lines each contain three integers $n, m, K$, representing the number of days the schedule lasts, the number of TAs, and the required total workload, respectively.

Output Format

Output $T$ lines, each containing one integer representing the answer to the corresponding query.

4
4 2 4
5 2 6
6 1 4
7 2 8

9
8
3
36

Hint

Sample Explanation

For the first query, $n = 4, m = 2, K = 4$.

Use $(A, B)$ to represent a duty schedule, where $A$ is the set of duty days for TA $1$, and $B$ is the set of duty days for TA $2$. All schedules that satisfy the requirements are:

$$\begin{aligned} & ((1, 2), (1, 2)), ((1, 2), (2, 3)), ((1, 2), (3, 4)), \\ & ((2, 3), (1, 2)), ((2, 3), (2, 3)), ((2, 3), (3, 4)), \\ & ((3, 4), (1, 2)), ((3, 4), (2, 3)), ((3, 4), (3, 4)). \end{aligned}$$

Therefore, the answer is $9$.

Constraints and Assumptions

For $30\%$ of the testdata, $1 \le T \le 3$, $1 \le n \le 12$, $1 \le m \le 6$, $1 \le K \le 24$.

For $60\%$ of the testdata, $1 \le T \le 5$, $1 \le n \le 10^5$, $1 \le m \le 50$, $1 \le K \le 200$.

For all testdata, $1 \le T \le 5$, $1 \le n \le 10^{18}$, $1 \le m \le 200$, $1 \le K \le 800$.

Translated by ChatGPT 5