{"raw_statement":[{"iden":"problem statement","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$."},{"iden":"constraints","content":"*   All values in input are integers.\n*   $1 \\leq N, M \\leq 2 \\times 10^5$\n*   $0 \\leq K \\leq N - 1$"},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$ $M$ $K$"},{"iden":"sample input 1","content":"3 2 1"},{"iden":"sample output 1","content":"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."},{"iden":"sample input 2","content":"100 100 0"},{"iden":"sample output 2","content":"73074801"},{"iden":"sample input 3","content":"60522 114575 7559"},{"iden":"sample output 3","content":"479519525"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}