题目描述

$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$

输出格式

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

题目大意

现在有一个 $1\times N$ 的格子和 $C$ 种颜色。

每一个格子上都涂了这 $C$ 种颜色的其中一种，并且任意相邻的 $K$ 个格子最多有两种不同的颜色。

准确地说，对于每一个 $i(1\le i\le N-K+1)$ ，格子 $i,i+1,\cdots,i+K-1$ 中，最多存在两种不同颜色。

求出有多少种方案给这些格子染色，对 $998244353$ 取模。

3 3 3

21

10 5 2

1024

998 244 353

952364159

提示

制約

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