AT_abc279_g [ABC279G] At Most 2 Colors

[problemUrl]: https://atcoder.jp/contests/abc279/tasks/abc279_g $ 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 $ で割った余りを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ K $ $ C $

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

### 制約 - 入力は全て整数 - $ 2\ \le\ K\ \le\ N\ \le\ 10^6 $ - $ 1\ \le\ C\ \le\ 10^9 $ ### Sample Explanation 1 この入力では、マス目は $ 1\ \times\ 3 $ です。 連続する $ 3 $ マスの中で高々 $ 2 $ 色しか現れないように塗る方法は、考えうる全ての塗り方 $ 27 $ 通りから全てのマスを異なる色で塗る $ 6 $ 通りを引いた $ 21 $ 通りです。 ### Sample Explanation 2 $ C=2 $ なので、どのように塗っても連続する $ K $ マスには高々 $ 2 $ 色しか含まれません。 ### Sample Explanation 3 $ 998244353 $ で割った余りを出力してください。