题目描述

有一个格子网格，包含 $1 \times N$ 个正方形，编号为 $1,2,\ldots,N$。

Takahashi 准备了 $C$ 种颜料，并用这 $C$ 种颜料之一对每个正方形进行了染色。
然后，在任意连续的 $K$ 个正方形中，最多只有两种颜色。
具体地说，对于每个满足 $1 \leq i \leq N-K+1$ 的整数 $i$，正方形 $i,i+1,\ldots,i+K-1$ 中最多只有两种颜色。

Takahashi 有多少种涂色方式？
由于数字可能很大，请将答案对 $998244353$ 取模。

约束条件

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

输入

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

$N$ $K$ $C$

输出

以整数形式打印答案。

样例输入 1

3 3 3

样例输出 1

21

在这个输入示例中，我们有一个 $1 \times 3$ 的网格。
在 $27$ 种涂色方式中，有 $6$ 种方式是用不同的颜色对所有正方形进行涂色的，剩余的 $21$ 种方式是在任意连续的三个正方形中最多只有两种颜色。

样例输入 2

10 5 2

样例输出 2

1024

由于 $C=2$，不论如何将正方形进行涂色，任意连续的 $K$ 个正方形中最多只有两种颜色。

样例输入 3

998 244 353

样例输出 3

952364159

将答案对 $998244353$ 取模后打印。