题目描述

在整数序列展示会上，将整数序列聚集在一起并进行评估。在这里，评估每个长度为 $N$ 的整数序列，该序列由介于 $1$ 和 $K$（包括边界）之间的整数组成，并给它一个介于 $1$ 和 $M$（包括边界）之间的整数分数。

打印出在 $1$ 和 $M$（包括边界）之间为每个评估的序列分配分数的方式数，取模 $998244353$。

这里，当两种方式在某个评估的序列 $A = (A_1, A_2, \ldots, A_N)$ 上给出不同的分数时，我们称它们是不同的方式。

约束条件

• $1 \leq N, K, M \leq 10^{18}$
• $N$、$K$ 和 $M$ 是整数。

输入

从标准输入获取以下格式的输入：

$N$ $K$ $M$

输出

打印出在 $1$ 和 $M$（包括边界）之间为每个评估的序列分配分数的方式数，取模 $998244353$。

示例输入 1

2 2 2

示例输出 1

16

有四个序列被评估：$(1, 1)$、$(1, 2)$、$(2, 1)$ 和 $(2, 2)$。有 $16$ 种方式可以在 $1$ 和 $2$（包括边界）之间为这些序列分配分数，如下所示。

• 将 $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$。

示例输入 2

3 14 15926535

示例输出 2

109718301

请务必将计数取模 $998244353$ 后输出。