题目描述

小蓝要为一门课程安排助教值班表。值班表持续 $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$ 行，每行包含一个整数，表示对应询问的答案。

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

9
8
3
36

提示

【样例说明】

对于第一组询问，$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$。