{"problem":{"name":"At Most 2 Colors","description":{"content":"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 mo","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc279_g"},"statements":[{"statement_type":"Markdown","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$.\n\n## Constraints\n\n*   All values in the input are integers.\n*   $2 \\le K \\le N \\le 10^6$\n*   $1 \\le C \\le 10^9$\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$ $K$ $C$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc279_g","tags":[],"sample_group":[["3 3 3","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."],["10 5 2","1024\n\nSince $C=2$, no matter how the squares are painted, there are at most two colors in any consecutive $K$ squares."],["998 244 353","952364159\n\nPrint the number modulo $998244353$."]],"created_at":"2026-03-03 11:01:13"}}