G - 最多2种颜色

得分：$600$ 分

题目描述

有一个长为 $1 \times N$ 的网格，从左到右编号为 $1,2,\dots,N$。

Takahashi 准备了 $C$ 种颜色的颜料，将每个方块涂成其中的一种颜色。
然后，任意连续的 $K$ 个方块中至多有两种颜色。
具体地说，对于满足 $1 \le i \le N-K+1$ 的每个整数 $i$，方块 $i,i+1,\dots,i+K-1$ 中至多有两种颜色。

Takahashi 总共有多少种涂色方案？
由于这个数字可能非常大，对 $998244353$ 取模后输出结果。

约束

• 输入中的所有值均为整数。
• $2 \le K \le N \le 10^6$
• $1 \le C \le 10^9$

输入

从标准输入中以下列格式给出：

$N$ $K$ $C$

输出

输出一个整数表示答案。

3 3 3

21

在这个样例中，我们有一个 $1 \times 3$ 的网格。
在涂色的所有 $27$ 种方式中，有 $6$ 种方案所有的方块颜色各不相同，而剩下的 $21$ 种方案中任意连续的三个方块中至多有两种颜色。

10 5 2

1024

由于 $C=2$，无论方块的涂色如何，任意连续的 $K$ 个方块中至多有两种颜色。

998 244 353

952364159

输出结果对 $998244353$ 取模后的值。