配点 : $500$ 点

問題文

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

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

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

制約

• $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)$ の $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$ を出力します。

3 14 15926535

109718301

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