102796: [AtCoder]ABC279 G - At Most 2 Colors

Problem Statement

There is a grid with $1 \times N$ squares, numbered $1,2,\dots,N$ from left to right.

Takahashi prepared paints of $C$ colors and painted each square in one of the $C$ colors.
Then, there were at most two colors in any consecutive $K$ squares.
Formally, for every integer $i$ such that $1 \le i \le N-K+1$, there were at most two colors in squares $i,i+1,\dots,i+K-1$.

In how many ways could Takahashi paint the squares?
Since this number can be enormous, find it modulo $998244353$.

Constraints

• All values in the input are integers.
• $2 \le K \le N \le 10^6$
• $1 \le C \le 10^9$

Input

The input is given from Standard Input in the following format:

$N$ $K$ $C$

Output

Print the answer as an integer.

Sample Input 1

3 3 3

Sample Output 1

21

In this input, we have a $1 \times 3$ grid.
Among the $27$ ways to paint the squares, there are $6$ ways to paint all squares in different colors, and the remaining $21$ ways are such that there are at most two colors in any consecutive three squares.

Sample Input 2

10 5 2

Sample Output 2

1024

Since $C=2$, no matter how the squares are painted, there are at most two colors in any consecutive $K$ squares.

Sample Input 3

998 244 353

Sample Output 3

952364159

Print the number modulo $998244353$.

问题描述

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

高桥准备了$C$种颜色的颜料，并将每个正方形涂成$C$种颜色中的一种。
然后，在任何连续的$K$个正方形中最多有两种颜色。
正式地说，对于任意整数$i$，满足$1 \le i \le N-K+1$，在正方形$i,i+1,\dots,i+K-1$中最多有两种颜色。

高桥可以有多少种涂色方式呢？
由于这个数可能非常大，所以要求它模$998244353$的结果。

约束条件

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

输入

输入是通过标准输入给出的，格式如下：

$N$ $K$ $C$

输出

打印出答案作为整数。

样例输入 1

3 3 3

样例输出 1

21

在这个输入中，我们有一个$1 \times 3$的网格。
在所有涂色方式中，有$6$种方式将所有正方形涂成不同的颜色，剩下的$21$种方式是使任何连续三个正方形中最多有两种颜色。

样例输入 2

10 5 2

样例输出 2

1024

因为$C=2$，无论怎样涂色，任何连续的$K$个正方形中最多有两种颜色。

样例输入 3

998 244 353

样例输出 3

952364159

打印出模$998244353$的结果。