整数序列品评会

题目描述

一场把整数序列集中起来评判优劣的“整数序列品评会”正在举行。

品评会上，所有由 $1$ 以上 $K$ 以下的整数组成、长度为 $N$ 的整数序列都是审查对象，并且要对每个审查对象给出一个 $1$ 以上 $M$ 以下的整数分数。

请输出“对每个审查对象给出 $1$ 以上 $M$ 以下整数分数的方法”有多少种，对 $998244353$ 取模。

这里，两种方法不同是指：存在某个审查对象序列 $A = (A_1, A_2, \ldots, A_N)$，使得两种方法给 $A$ 打的分数不同。

输入格式

输入按以下格式从标准输入给出：

$N$ $K$ $M$

输出格式

输出“对每个审查对象给出 $1$ 以上 $M$ 以下整数分数的方法”的种数对 $998244353$ 取模的结果。

样例

2 2 2

16

审查对象序列是 $(1, 1), (1, 2), (2, 1), (2, 2)$ 这 $4$ 个。“给每个审查对象打出 $1$ 以上 $2$ 以下的整数分数的方法”有以下 $16$ 种：

给 $(1, 1)$ 记 $1$ 分、$(1, 2)$ 记 $1$ 分、$(2, 1)$ 记 $1$ 分、$(2, 2)$ 记 $1$ 分的方法 给 $(1, 1)$ 记 $1$ 分、$(1, 2)$ 记 $1$ 分、$(2, 1)$ 记 $1$ 分、$(2, 2)$ 记 $2$ 分的方法 给 $(1, 1)$ 记 $1$ 分、$(1, 2)$ 记 $1$ 分、$(2, 1)$ 记 $2$ 分、$(2, 2)$ 记 $1$ 分的方法 给 $(1, 1)$ 记 $1$ 分、$(1, 2)$ 记 $1$ 分、$(2, 1)$ 记 $2$ 分、$(2, 2)$ 记 $2$ 分的方法 $\cdots$
给 $(1, 1)$ 记 $2$ 分、$(1, 2)$ 记 $2$ 分、$(2, 1)$ 记 $2$ 分、$(2, 2)$ 记 $2$ 分的方法

因此输出 $16$。

3 14 15926535

109718301

注意要输出对 $998244353$ 取模后的结果。

数据范围

• $1 \le N, K, M \le 10^{18}$
• $N, K, M$ 是整数