/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
1 \times N のマス目があり、マスには左から 1,2,\dots,N の番号が付いています。
高橋君は C 色の絵の具を用意し、各マスを C 色のいずれかで塗りました。
すると、どの連続する K マスを見ても高々 2 色しか現れませんでした。
厳密には、 1 \le i \le N-K+1 を満たす全ての整数 i について、マス i,i+1,\dots,i+K-1 には高々 2 色しか現れませんでした。
高橋君の色の塗り方として考えられるものは何通りですか？
この数は非常に大きくなる場合があるので、 998244353 で割った余りを求めてください。
制約
- 入力は全て整数
- 2 \le K \le N \le 10^6
- 1 \le C \le 10^9
入力
入力は以下の形式で標準入力から与えられる。
N K C
出力
答えを整数として出力せよ。
入力例 1
3 3 3
出力例 1
21
この入力では、マス目は 1 \times 3 です。
連続する 3 マスの中で高々 2 色しか現れないように塗る方法は、考えうる全ての塗り方 27 通りから全てのマスを異なる色で塗る 6 通りを引いた 21 通りです。
入力例 2
10 5 2
出力例 2
1024
C=2 なので、どのように塗っても連続する K マスには高々 2 色しか含まれません。
入力例 3
998 244 353
出力例 3
952364159
998244353 で割った余りを出力してください。
Score : 600 points
Problem Statement
There is a grid with 1 \times N squares, numbered 1,2,\dots,N from left to right.
Takahashi prepared paints of C colors and painted each square in one of the C colors.
Then, there were at most two colors in any consecutive K squares.
Formally, for every integer i such that 1 \le i \le N-K+1, there were at most two colors in squares i,i+1,\dots,i+K-1.
In how many ways could Takahashi paint the squares?
Since this number can be enormous, find it modulo 998244353.
Constraints
- All values in the input are integers.
- 2 \le K \le N \le 10^6
- 1 \le C \le 10^9
Input
The input is given from Standard Input in the following format:
N K C
Output
Print the answer as an integer.
Sample Input 1
3 3 3
Sample Output 1
21
In this input, we have a 1 \times 3 grid.
Among the 27 ways to paint the squares, there are 6 ways to paint all squares in different colors, and the remaining 21 ways are such that there are at most two colors in any consecutive three squares.
Sample Input 2
10 5 2
Sample Output 2
1024
Since C=2, no matter how the squares are painted, there are at most two colors in any consecutive K squares.
Sample Input 3
998 244 353
Sample Output 3
952364159
Print the number modulo 998244353.