{"raw_statement":[{"iden":"problem statement","content":"You are given integers $N, M, K$.  \nFor each $m = 1, 2, \\dots, M$, solve the following problem:\n\n> There are $N$ balls numbered $1$ through $N$, and $m+1$ boxes numbered $0$ through $m$.  \n> Box $0$ can hold at most $K$ balls. The other boxes have no upper limit.  \n> Find the number of ways to place all $N$ balls into the boxes, modulo $998244353$.  \n> Two placements are considered different if there exists at least one ball that is placed in different boxes between the two placements."},{"iden":"constraints","content":"*   $1 \\leq N \\leq 10^5$\n*   $1 \\leq M \\leq 10^5$\n*   $1 \\leq K \\leq N$\n*   All input values are integers"},{"iden":"input","content":"The 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":"4\n20\n\nConsider the case $m=1$. There are $4$ valid placements of the balls:\n\n*   Put balls $1,2,3$ into box $1$.\n*   Put ball $1$ into box $0$, and balls $2,3$ into box $1$.\n*   Put ball $2$ into box $0$, and balls $1,3$ into box $1$.\n*   Put ball $3$ into box $0$, and balls $1,2$ into box $1$."},{"iden":"sample input 2","content":"12345 5 6789"},{"iden":"sample output 2","content":"583034791\n982161077\n613932842\n770852810\n194914198"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}