UOJ Logo Universal Online Judge

UOJ

附件下载 统计

虱子国国王 —— 伟大 NIT,计划在虱子国发展经济。虱子国一共有 $n$ 个城市,第 $i$ ($1\leq i\lt n$) 个城市和第 $i+1$ 个城市之间有道路相连,并且 $n$ 号和 $1$ 号城市之间也有道路。

伟大 NIT 是一位事事躬亲的好国王,他会开着载货量为 $m$ 份货物的货车在虱子国做贸易,从 $1$ 号城市出发,沿道路经过 $2,3,\ldots,n$ 号城市,最后回到 $1$ 号城市。

伟大 NIT 初始会携带一些货物。伟大 NIT 沿道路到达一个城市时,若货车此时有 $x$ 份货物,那么他会购入 $\min(m-x,K)$ 份货物,然后卖出若干份货物(也可以不卖)。为了防止突发情况,伟大 NIT 不能卖出全部存货。此外,伟大 NIT 还希望最后离开 $1$ 号城市时带走的货物和他初始携带的货物数量相同,方便之后的行动。

注意,伟大 NIT 出发时并不会在 $1$ 号城市贸易,但是最后返回 $1$ 号城市时会进行一次贸易。初始时载货量可以为 $1$ 到 $m$ 中的任意整数,不能空载。

伟大 NIT 想知道,他有多少种不同的贸易计划。两个计划不同当且仅当在某个城市卖出的货物份数不同或初始载货量不同。因为计划数非常多,你只需要输出答案对 $998244353$ 取模后的结果。

输入格式

一行三个非负整数,分别表示 $n,m,K$。

输出格式

一行一个整数表示你的答案,对 $998244353$ 取模。

样例一

input

2 3 1

output

7

explanation

合法的方案是 $(1,1),(2,2),(3,3),(1,2),(2,1),(2,3),(3,2)$,共 $7$ 种,其中 $(x,y)$ 表示离开 $1$ 城和 $2$ 城时的载货量为 $x,y$。

样例二

input

40 100 10

output

443737370

explanation

写个暴力算一下即可。

限制与约定

子任务编号 $n\leqslant $ $m\leqslant $ $K\leqslant $ 分值
$1$ $10^9$ $10^5$ $0$ $2$
$2$ $10^3$ $10^3$ $10$ $18$
$3$ $10^9$ $100$ $10$ $20$
$4$ $100$ $10^9$ $10$ $20$
$5$ $10000$ $10^9$ $10$ $20$
$6$ $10^9$ $10^5$ $10$ $20$

对于所有数据,$2\leq n\leq 10^9,1\leq m\leq 10^9,0\leq K\leq 10$。请选手注意子任务的数据范围

时间限制:$\texttt{5s}$

空间限制:$\texttt{256MB}$