题目描述

有一个长度为 $n$ 的整数序列，它里面的每一个元素的值都在 $[1,k]$ 范围内。对于每一个满足条件的序列，都给出一个值在 $[1,m]$ 之间的得分。请求出有多少种不同的方法满足题目要求？答案对 $998244353$ 取模。

输入格式

第一行输入三个空格隔开的整数 $n,k,m$

输出格式

打印在 $1$ 和 $M$ 之间给每个被评估序列打分的方式的数量，模数为 $998244353$ 。

2 2 2

16

3 14 15926535

109718301

提示

$1 \le n,k,m \le 10^{18}$，且上述三数均为整数。

Sample Explanation 1

评估了四个序列： $(1, 1)$ 、 $(1, 2)$ 、 $(2, 1)$ 和 $(2, 2)$ 。在 $1$ 和 $2$ 之间，有 $16$ 种方法可以给每个序列打分，具体如下。

• 给 $1$ 打分到 $(1, 1)$，给 $1$ 打分到 $(1, 2)$ ，给 $1$ 打分到 $(2, 1)$ ，给 $1$ 打分到 $(2, 2)$ 。
• 将 $1$ 改为 $(1, 1)$ ，将 $1$ 改为 $(1, 2)$ ，将 $1$ 改为 $(2, 1)$ ，将 $2$ 改为 $(2, 2)$ 。
• 把 $1$ 改为 $(1, 1)$ ，把 $1$ 改为 $(1, 2)$ ，把 $2$ 改为 $(2, 1)$ ，把 $1$ 改为 $(2, 2)$ 。
• 将 $1$ 改为 $(1, 1)$ ，将 $1$ 改为 $(1, 2)$ ，将 $2$ 改为 $(2, 1)$ ，将 $2$ 改为 $(2, 2)$ 。
• $\cdots$
• 将 $2$ 改为 $(1, 1)$ ，将 $2$ 改为 $(1, 2)$ ，将 $2$ 改为 $(2, 1)$ ，将 $2$ 改为 $(2, 2)$ 。

因此，我们打印出 $16$ 。