/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 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 で割ったあまりを出力せよ。
入力例 1
2 2 2
出力例 1
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 を出力します。
入力例 2
3 14 15926535
出力例 2
109718301
998244353 で割ったあまりを出力することに注意してください。
Score : 500 points
Problem Statement
Integer Sequence Exhibition is taking place, where integer sequences are gathered in one place and evaluated. Here, every integer sequence of length N consisting of integers between 1 and K (inclusive) is evaluated and given an integer score between 1 and M (inclusive).
Print the number, modulo 998244353, of ways to give each of the evaluated sequences a score between 1 and M.
Here, two ways are said to be different when there is an evaluated sequence A = (A_1, A_2, \ldots, A_N) that is given different scores by the two ways.
Constraints
- 1 \leq N, K, M \leq 10^{18}
- N, K, and M are integers.
Input
Input is given from Standard Input in the following format:
N K M
Output
Print the number, modulo 998244353, of ways to give each of the evaluated sequences a score between 1 and M.
Sample Input 1
2 2 2
Sample Output 1
16
Four sequences are evaluated: (1, 1), (1, 2), (2, 1), and (2, 2). There are 16 ways to give each of these sequences a score between 1 and 2, as follows.
- Give 1 to (1, 1), 1 to (1, 2), 1 to (2, 1), and 1 to (2, 2)
- Give 1 to (1, 1), 1 to (1, 2), 1 to (2, 1), and 2 to (2, 2)
- Give 1 to (1, 1), 1 to (1, 2), 2 to (2, 1), and 1 to (2, 2)
- Give 1 to (1, 1), 1 to (1, 2), 2 to (2, 1), and 2 to (2, 2)
- \cdots
- Give 2 to (1, 1), 2 to (1, 2), 2 to (2, 1), and 2 to (2, 2)
Thus, we print 16.
Sample Input 2
3 14 15926535
Sample Output 2
109718301
Be sure to print the count modulo 998244353.