{"raw_statement":[{"iden":"problem statement","content":"There is a grid with $1 \\times N$ squares, numbered $1,2,\\dots,N$ from left to right.\nTakahashi prepared paints of $C$ colors and painted each square in one of the $C$ colors.  \nThen, there were at most two colors in any consecutive $K$ squares.  \nFormally, 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$.\nIn how many ways could Takahashi paint the squares?  \nSince this number can be enormous, find it modulo $998244353$."},{"iden":"constraints","content":"*   All values in the input are integers.\n*   $2 \\le K \\le N \\le 10^6$\n*   $1 \\le C \\le 10^9$"},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$ $K$ $C$"},{"iden":"sample input 1","content":"3 3 3"},{"iden":"sample output 1","content":"21\n\nIn this input, we have a $1 \\times 3$ grid.  \nAmong 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."},{"iden":"sample input 2","content":"10 5 2"},{"iden":"sample output 2","content":"1024\n\nSince $C=2$, no matter how the squares are painted, there are at most two colors in any consecutive $K$ squares."},{"iden":"sample input 3","content":"998 244 353"},{"iden":"sample output 3","content":"952364159\n\nPrint the number modulo $998244353$."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}