問題文

$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$ で割った余りを出力してください。