atcoder#ABC279G. [ABC279G] At Most 2 Colors

[ABC279G] At Most 2 Colors

Score : 600600 points

Problem Statement

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

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

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

Constraints

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

Input

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

NN KK CC

Output

Print the answer as an integer.

3 3 3
21

In this input, we have a 1×31 \times 3 grid. Among the 2727 ways to paint the squares, there are 66 ways to paint all squares in different colors, and the remaining 2121 ways are such that there are at most two colors in any consecutive three squares.

10 5 2
1024

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

998 244 353
952364159

Print the number modulo 998244353998244353.