Integer Sequence Fair

题目描述

Integer Sequence Exhibition 正在举行，整数序列被聚集到一个地方并被评估。这里，每一个长度为 $N$、由 $1$ 到 $K$（包括端点）之间的整数组成的整数序列都会被评估并被赋予一个介于 $1$ 到 $M$（包括端点）之间的整数分数。 输出将每一个被评估的序列赋予 $1$ 到 $M$ 之间分数的方法数，对 $998244353$ 取模。 当存在一个被评估的序列 $A = (A_1, A_2, \ldots, A_N)$ 在两种方法中被赋予不同分数时，认为这两种方法不同。

输入格式

输入从标准输入按以下格式给出： $N$ $K$ $M$

输出格式

输出将每一个被评估的序列赋予 $1$ 到 $M$ 之间分数的方法数，对 $998244353$ 取模。

2 2 2

16

3 14 15926535

109718301

提示

$1 \leq N, K, M \leq 10^{18}$ $N$、$K$ 和 $M$ 为整数。一共有四个序列被评估：$(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$。
请务必对 $998244353$ 取模后输出计数。

标签: AtCoder|abc228E

来源

AtCoder|abc228E