当前没有测试数据。

E - 整数序列的公平性

分值: $500$ 点

问题描述

在整数序列展览会上，整数序列被收集在一起并进行评估。在这里，所有长度为 $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$。

2 2 2

16

有四个序列将被评估：$(1, 1)$，$(1, 2)$，$(2, 1)$ 和 $(2, 2)$。有 $16$ 种方法将它们中的每一个序列分配给介于 $1$ 到 $2$ 的分数，如下所示。

• 将 $(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$ 后再进行输出。