U381274 小Y的糖果

小Y共有 $m$ 个收纳盒，编号分别为 $1, 2, \cdots, m$。每个收纳盒的最大容量均为 $k$。TA 准备将自己在万圣节收到的 $n$ 颗糖果装到这些收纳盒里，请你帮忙计算一下共有多少种装糖果的方法。 记某种装糖果的方法为 $[a_1, a_2, \cdots, a_m]$ ，其中，$a_i$ 表示编号为 $i$ 的盒子装有 $a_i$ 颗糖果。 $[a_1, a_2, \cdots, a_m]$ 和 $[a_1', a_2', \cdots, a_m']$ 两种装糖果的方法不同，当且仅当 $\exist\ i \in [1, m], a_i \neq a_i'$。

一行，三个整数 $n, m, k$ $(1 \leq n,m,k \leq 10^6)$。

一行，一个整数，表示装糖果的方法数。 由于答案可能很大，你只需要回答对 $998244353$ 取模后的结果即可。

样例 1 解释： 将 $2$ 颗糖果装入 $3$ 个盒子，并且每个盒子中最多装 $1$ 颗糖果，有以下三种装法： $[1, 1, 0]$ $[0, 1, 1]$ $[1, 0, 1]$ 提示： 考虑一个质数 $P$ ，如果两个整数 $x$、$y$ 满足 $x \mod P = y \mod P$，那么就称 $x$、$y$ 在模 $P$ 意义下等价，记作 $x \equiv y \pmod P$。比如，$17 \equiv 3 \pmod 7$、$-1 \equiv 6 \pmod 7$。 可以证明，在模 $P$ 意义下，对于任意一个 $x \in [1, P - 1]$，都存在唯一一个 $y \in [1, P - 1]$，使得 $xy \equiv 1 \pmod{P}$。这个 $y$ 就是 $x$ 的逆元，记作 $x^{-1}$ 或者 $\dfrac{1}{x}$。比如，$2 \times 3 \equiv 6 \equiv 1 \pmod 5$，所以$\dfrac{1}{2} \equiv 3 \pmod 5$。 若正整数 $x, k \in [1, P - 1] $，显然有 $P + kx \equiv kx \pmod P$，等式两边同时乘以 $\dfrac{1}{x(P + kx)}$ 得 $\dfrac{1}{x} \equiv \dfrac{k}{P + kx} \pmod P$，$x > 1$ 时取 $k = -\lfloor \dfrac{P}{x} \rfloor$，得递推式 $\dfrac{1}{x} \equiv -\lfloor \dfrac{P}{x}\rfloor\dfrac{1}{P \mod x} \pmod P$。 可以直接使用以下程序实现求前 $n$ 个数的逆元$1^{-1}, 2^{-1}, \cdots, n^{-1} \pmod P$，以及模意义下的除法运算： ```c #define MAXN 2000001 const int P = 998244353; int INV[MAXN]; void init_inv(int n) { INV[1] = 1; for (int i = 2; i