AT_abc228_e [ABC228E] Integer Sequence Fair

[problemUrl]: https://atcoder.jp/contests/abc228/tasks/abc228_e 整数列を一堂に集めてその優劣を定める、整数列品評会が行われます。 品評会では、$ 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 $ で割ったあまりを出力せよ。

### 制約 - $ 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 $ で割ったあまりを出力することに注意してください。