分数: 600 点
问题陈述
有一个网格 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 网格。
其中 27 绘制正方形的方法,有 6 将所有方块涂成不同颜色的方法,其余的 21 的方式是在任何连续的三个方块中最多有两种颜色。
示例输入 2
10 5 2
示例输出 2
1024
自从 C=2,无论方块如何绘制,任意连续的最多有两种颜色 K 方块。
示例输入 3
998 244 353
示例输出 3
952364159
打印数字模数 998244353.