P16811 [Lanqiao Cup 2026 National Python A] Course Duty Schedule

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$.

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 $T$ lines, each containing one integer representing the answer to the corresponding query.

### 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