{"problem":{"name":"Sugoroku 5","description":{"content":"There is a board game with $N+1$ squares: square $0$, square $1$, $\\dots$, square $N$.   You have a die (dice) that rolls an integer between $1$ and $K$, inclusive, with equal probability for each out","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":12000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc345_g"},"statements":[{"statement_type":"Markdown","content":"There is a board game with $N+1$ squares: square $0$, square $1$, $\\dots$, square $N$.  \nYou have a die (dice) that rolls an integer between $1$ and $K$, inclusive, with equal probability for each outcome.  \nYou start on square $0$. You repeat the following operation until you reach square $N$:\n\n*   Roll the dice. Let $x$ be the current square and $y$ be the rolled number, then move to square $\\min(N, x + y)$.\n\nLet $P_i$ be the probability of reaching square $N$ after exactly $i$ operations. Calculate $P_1, P_2, \\dots, P_N$ modulo $998244353$.\nWhat is probability modulo $998244353$? It can be proved that the sought probabilities will always be rational numbers. Under the constraints of this problem, it can also be proved that when expressing the values as $\\frac{P}{Q}$ using two coprime integers $P$ and $Q$, there is exactly one integer $R$ satisfying $R \\times Q \\equiv P\\pmod{998244353}$ and $0 \\leq R < 998244353$. Find this $R$.\n\n## Constraints\n\n*   $1 \\leq K \\leq N \\leq 2 \\times 10^5$\n*   $N$ and $K$ are integers.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$ $K$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc345_g","tags":[],"sample_group":[["3 2","0\n249561089\n748683265\n\nFor example, you reach square $N$ after exactly two operations when the die rolls the following numbers:\n\n*   A $1$ on the first operation, and a $2$ on the second operation.\n*   A $2$ on the first operation, and a $1$ on the second operation.\n*   A $2$ on the first operation, and a $2$ on the second operation.\n\nTherefore, $P_2 = \\left( \\frac{1}{2} \\times \\frac{1}{2} \\right) \\times 3 = \\frac{3}{4}$. We have $249561089 \\times 4 \\equiv 3 \\pmod{998244353}$, so print $249561089$ for $P_2$."],["5 5","598946612\n479157290\n463185380\n682000542\n771443236"],["10 6","0\n166374059\n207967574\n610038216\n177927813\n630578223\n902091444\n412046453\n481340945\n404612686"]],"created_at":"2026-03-03 11:01:14"}}