{"problem":{"name":"Colorful Blocks","description":{"content":"There are $N$ blocks arranged in a row. Let us paint these blocks. We will consider two ways to paint the blocks different if and only if there is a block painted in different colors in those two ways","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc167_e"},"statements":[{"statement_type":"Markdown","content":"There are $N$ blocks arranged in a row. Let us paint these blocks.\nWe will consider two ways to paint the blocks different if and only if there is a block painted in different colors in those two ways.\nFind the number of ways to paint the blocks under the following conditions:\n\n*   For each block, use one of the $M$ colors, Color $1$ through Color $M$, to paint it. It is not mandatory to use all the colors.\n*   There may be at most $K$ pairs of adjacent blocks that are painted in the same color.\n\nSince the count may be enormous, print it modulo $998244353$.\n\n## Constraints\n\n*   All values in input are integers.\n*   $1 \\leq N, M \\leq 2 \\times 10^5$\n*   $0 \\leq K \\leq N - 1$\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$ $M$ $K$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc167_e","tags":[],"sample_group":[["3 2 1","6\n\nThe following ways to paint the blocks satisfy the conditions: `112`, `121`, `122`, `211`, `212`, and `221`. Here, digits represent the colors of the blocks."],["100 100 0","73074801"],["60522 114575 7559","479519525"]],"created_at":"2026-03-03 11:01:14"}}