{"problem":{"name":"Sugoroku 4","description":{"content":"Takahashi is playing sugoroku, a board game. The board has $N+1$ squares, numbered $0$ to $N$. Takahashi starts at square $0$ and goes for square $N$. The game uses a roulette wheel with $M$ numbers f","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc275_e"},"statements":[{"statement_type":"Markdown","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$.\n\n## Constraints\n\n*   $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.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$ $M$ $K$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc275_e","tags":[],"sample_group":[["2 2 1","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$."],["10 5 6","184124175"],["100 1 99","0"]],"created_at":"2026-03-03 11:01:14"}}