题目描述

整数列を一堂に集めてその優劣を定める、整数列品評会が行われます。 品評会では、$1$ 以上 $K$ 以下の整数からなる長さ $N$ の整数列すべてが審査対象となり、 審査対象の数列それぞれに対して $1$ 以上 $M$ 以下の整数の点数をつけます。

「審査対象の数列それぞれに対して $1$ 以上 $M$ 以下の整数の点数をつける方法」が何通りあるかを $998244353$ で割ったあまりを出力してください。

ただし、$2$ つの方法が異なるとは「審査対象となるある数列 $A\ =\ (A_1,\ A_2,\ \ldots,\ A_N)$ が存在して、 $A$ に対してつける点数が $2$ つの方法で異なる」ことを言います。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $K$ $M$

输出格式

「審査対象の数列それぞれに対して $1$ 以上 $M$ 以下の整数の点数をつける方法」が何通りあるかを $998244353$ で割ったあまりを出力せよ。

题目大意

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

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

2 2 2

16

3 14 15926535

109718301

提示

制約

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

Sample Explanation 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$ を出力します。

Sample Explanation 2

$998244353$ で割ったあまりを出力することに注意してください。