该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“赛后递交”以递交本题。

题目描述

有一只条状的“蛄踊者”唱着“爱你孤身走暗巷，爱你不跪的模样...”在数轴上蛄踊。

初始时，蛄踊者的头尾都在数轴 $0$ 点处，他的尾、头的位置分别为 $l_i,r_i$，即初始 $l_0=r_0=0$。

他每次一屈一伸的向数轴正方向移动，保证每次移动后 $l_i\le r_i$，并且有 $l_i < l_{i+1}, r_i < r_{i+1}$。

小Z要为蛄踊者的移动进行计分，数轴上每个整点 $x$ 都有一个计数 $c_x$，初始时对所有整点 $x$ 均有 $c_x=0$。由于蛄踊者唱歌声音太大了，所以小Z不愿意接触蛄踊者的头部，他会将区间 $[l_i, r_i)$ 之间的整点的计数 $c_j(l_i \leqslant j < r_i)$ 加 $1$。

保证蛄踊者在 $n$ 次移动之后都没有超过数轴上限 $m$。定义这 $n$ 次蛄踊的总得分为

$$I = \sum_{i = 1}^m c_i^k$$

对于所有满足上述条件的移动轨迹，蛄踊者的总得分 $I$ 的和是多少？答案对 $998,244,353$ 取模。

输入格式

仅一行，输入三个正整数 $n, m, k$。

输出格式

输出一个整数，表示答案，对 $998,244,353$ 取模。

输入输出样例

2 4 4

40

样例 $\tt \#1$说明

3 5 3

132

114 514 300

921588182

数据范围

对于 $100\%$ 的数据，保证 $1 \leqslant nm \leqslant 10^5$，$1 \leqslant n,m \leqslant 10^5$，$1 \leqslant k \leqslant 10^9$。

测试点编号	$n$	$m$	$k$
$1$	$\leqslant 10^5$	$\leqslant 6$	$\leqslant 10^9$
$2$
$3$
$4$		$\leqslant 40$	$= 1$
$5$
$6$			$= 998244352$
$7$
$8$	$= 1$	$\leqslant 350$	$\leqslant 10^9$
$9$	$= 2$
$10$
$11$	$\leqslant 10^5$		$= 1$
$12$			$= 998244352$
$13$	$= 1$	$\leqslant 10^5$	$\leqslant 10^9$
$14$	$= 2$
$15$			$= 1$
$16$	$= 3$
$17$			$= 998244352$
$18$			$= 998244352$
$19$	$\leqslant 10^5$		$\leqslant 10^9$
$20$