← 返回题目列表

AtCoder · abc279_g

G. 最多 2 种颜色

中文机器翻译题面 查看原题

分数: 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.