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$

输出格式

请输出一个整数，表示答案。

输入输出样例 #1

输入 #1

3 3 3

输出 #1

21

输入输出样例 #2

输入 #2

10 5 2

输出 #2

1024

输入输出样例 #3

输入 #3

998 244 353

输出 #3

952364159

说明/提示

限制条件

• 输入均为整数。
• $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 翻译