题目描述

你有一个长为 $n$ 的序列 $\left\{a_{n}\right\}$, 每个位置你可以填一个 $[0, m-1]$ 中的整数。

我们记 $\left\{a_{n}\right\}$ 的前缀和为 $\left\{s_{n}\right\}$, 即 $s_{i}=\sum_{j=1}^{i} a_{j}$ 。 问有多少个不同的序列 $\left\{a_{n}\right\}$ 满足至少有 $k$ 个 $s_{i}$ 是 $m$ 的倍数。 答案可能很大，请输出答案对 $998244353$ 取模的结果。

输入格式

第一行一个整数 $T$ 表示数据组数。

以下 $T$ 行, 每行三个整数分别表示 $n, m, k$ 。

输出格式

对于每组数据, 输出一行一个整数表示答案对 $998244353$ 取模的结果。

样例

2
2 2 3
3 2 2

0
4

对于第一组数据，没有满足条件的序列 $\left\{a_{n}\right\}$ 。 对于第二组数据, 共有四个满足条件的序列 $\left\{a_{n}\right\}$ 。

分别是 $\{0,0,0\},\{0,0,1\},\{0,1,1\},\{1,1,0\}$ 。

子任务

对于 $30 \%$ 的数据, 满足 $n, k \leq 1000$。

对于 $60 \%$ 的数据, 满足 $n, k \leq 3 \times 10^{4}, m \leq 10^{6}$。

对于 $100 \%$ 的数据，满足 $T \leq 10,2 \leq n \leq 10^{5}, \sum n \leq 5 \times 10^{5}, 0 \leq m, k \leq10^9$。