至多两种颜色

题目描述

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

高桥君准备了 $C$ 种颜色的颜料,给每个格子涂上了 $C$ 种颜色中的一种。

结果,任意连续的 $K$ 个格子中,最多只出现了两种颜色。

形式化地说,对每个满足 $1 \le i \le N-K+1$ 的整数 $i$,格子 $i,i+1,\dots,i+K-1$ 中最多出现两种颜色。

高桥君有多少种涂色方案?

由于这个数量可能非常巨大,请输出它对 $998244353$ 取模后的结果。

输入格式

输入按以下格式从标准输入给出:

$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$ 取模后的结果。

数据范围

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