配点 : $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$

出力

答えを整数として出力せよ。

3 3 3

21

この入力では、マス目は $1 \times 3$ です。 連続する $3$ マスの中で高々 $2$ 色しか現れないように塗る方法は、考えうる全ての塗り方 $27$ 通りから全てのマスを異なる色で塗る $6$ 通りを引いた $21$ 通りです。

10 5 2

1024

$C=2$ なので、どのように塗っても連続する $K$ マスには高々 $2$ 色しか含まれません。

998 244 353

952364159

$998244353$ で割った余りを出力してください。