AT_abc228_e [ABC228E] Integer Sequence Fair

题目描述

将所有整数列集中在一起，进行优劣评定的“整数列品评会”正在举行。在品评会上，所有由 $1$ 到 $K$ 之间的整数构成、长度为 $N$ 的整数列都将作为评审对象。对于每一个评审对象的数列，都要赋予一个 $1$ 到 $M$ 之间的整数分数。

请输出“对于每一个评审对象的数列赋予 $1$ 到 $M$ 之间的整数分数的方法数”，对 $998244353$ 取模后的结果。

这里，两种方法不同，是指“存在某个作为评审对象的数列 $A = (A_1, A_2, \ldots, A_N)$，对于 $A$ 所赋予的分数在两种方法下不同”。

输入格式

输入以如下格式从标准输入给出。

$N$ $K$ $M$

输出格式

请输出“对于每一个评审对象的数列赋予 $1$ 到 $M$ 之间的整数分数的方法数”，对 $998244353$ 取模后的结果。

输入输出样例 #1

输入 #1

2 2 2

输出 #1

16

输入输出样例 #2

输入 #2

3 14 15926535

输出 #2

109718301

说明/提示

限制条件

• $1 \leq N, K, M \leq 10^{18}$
• $N, K, M$ 均为整数

样例解释 1

作为评审对象的数列有 $(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$。

样例解释 2

请注意要对 $998244353$ 取模后输出。

由 ChatGPT 4.1 翻译