{"raw_statement":[{"iden":"problem statement","content":"Takahashi is playing sugoroku, a board game.\nThe board has $N+1$ squares, numbered $0$ to $N$. Takahashi starts at square $0$ and goes for square $N$.\nThe game uses a roulette wheel with $M$ numbers from $1$ to $M$ that appear with equal probability. Takahashi spins the wheel and moves by the number of squares indicated by the wheel. If this would send him beyond square $N$, he turns around at square $N$ and goes back by the excessive number of squares.\nFor instance, assume that $N=4$ and Takahashi is at square $3$. If the wheel shows $4$, the excessive number of squares beyond square $4$ is $3+4-4=3$. Thus, he goes back by three squares from square $4$ and arrives at square $1$.\nWhen Takahashi arrives at square $N$, he wins and the game ends.\nFind the probability, modulo $998244353$, that Takahashi wins when he may spin the wheel at most $K$ times.\nHow to print a probability modulo $998244353$It can be proved that the sought probability is always a rational number. Additionally, under the Constraints of this problem, when the sought probability is represented as an irreducible fraction $\\frac{y}{x}$, it is guaranteed that $x$ is not divisible by $998244353$.\nHere, there is a unique integer $z$ between $0$ and $998244352$ such that $xz \\equiv y \\pmod{998244353}$. Print this $z$."},{"iden":"constraints","content":"*   $M \\leq N \\leq 1000$\n*   $1 \\leq M \\leq 10$\n*   $1 \\leq K \\leq 1000$\n*   All values in the input 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":"2 2 1"},{"iden":"sample output 1","content":"499122177\n\nTakahashi wins in one spin if the wheel shows $2$. Therefore, the probability of winning is $\\frac{1}{2}$.\nWe have $2\\times 499122177 \\equiv 1 \\pmod{998244353}$, so the answer to be printed is $499122177$."},{"iden":"sample input 2","content":"10 5 6"},{"iden":"sample output 2","content":"184124175"},{"iden":"sample input 3","content":"100 1 99"},{"iden":"sample output 3","content":"0"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}