AT_abc279_g [ABC279G] At Most 2 Colors

有一个 $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$ ## 样例解释 1 对于该输入，格子为 $1 \times 3$。 在所有可能的 $27$ 种涂色方法中，去掉所有格子都涂不同颜色的 $6$ 种方案，剩下 $21$ 种方案满足任意连续 $3$ 个格子最多只出现 $2$ 种颜色。 ## 样例解释 2 由于 $C=2$，无论如何涂色，任意连续 $K$ 个格子中最多只会出现 $2$ 种颜色。 ## 样例解释 3 请输出对 $998244353$ 取模的结果。 由 ChatGPT 4.1 翻译