P16811 [蓝桥杯 2026 国 Python A] 课程值班

小蓝要为一门课程安排助教值班表。值班表持续 $n$ 天，共有 $m$ 名助教，编号为 $1$ 到 $m$。 每一天可以安排若干名助教值班。整份值班表需要满足以下要求： - 每名助教至少值班一次； - 为了方便交接，若某名助教在第 $i$ 天值班，则他也必须在第 $i - 1$ 天或第 $i + 1$ 天值班； - 为了避免过于疲劳，同一名助教不能连续值班 $3$ 天。 一份值班表的总工作量定义为所有助教的值班天数之和。也就是说，若第 $i$ 名助教一共值班 $c_i$ 天，则总工作量为： $$\begin{aligned} c_1 + c_2 + \dots + c_m \end{aligned}$$ 现在要求总工作量恰好为 $K$。请你计算有多少种值班表满足要求。由于答案可能很大，你只需要输出答案对 $998244353$ 取模后的结果即可。

第一行包含一个正整数 $T$，表示询问组数。 接下来 $T$ 行，每行包含三个整数 $n, m, K$，分别表示值班表持续的天数、助教人数以及要求的总工作量。

输出 $T$ 行，每行包含一个整数，表示对应询问的答案。

### 【样例说明】 对于第一组询问，$n = 4, m = 2, K = 4$。 用 $(A, B)$ 表示一种值班表，其中 $A$ 是 $1$ 号助教的值班日期，$B$ 是 $2$ 号助教的值班日期。所有满足要求的值班表为： $$\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}$$ 因此答案为 $9$。 ### 【评测用例规模与约定】 对于 $30\%$ 的评测用例，$1 \le T \le 3$, $1 \le n \le 12$, $1 \le m \le 6$, $1 \le K \le 24$; 对于 $60\%$ 的评测用例，$1 \le T \le 5$, $1 \le n \le 10^5$, $1 \le m \le 50$, $1 \le K \le 200$; 对于所有评测用例，$1 \le T \le 5$, $1 \le n \le 10^{18}$, $1 \le m \le 200$, $1 \le K \le 800$。