{"raw_statement":[{"iden":"problem statement","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$."},{"iden":"constraints","content":"*   $1 \\leq K \\leq N \\leq 2 \\times 10^5$\n*   $N$ and $K$ are integers."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$ $K$"},{"iden":"sample input 1","content":"3 2"},{"iden":"sample output 1","content":"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$."},{"iden":"sample input 2","content":"5 5"},{"iden":"sample output 2","content":"598946612\n479157290\n463185380\n682000542\n771443236"},{"iden":"sample input 3","content":"10 6"},{"iden":"sample output 3","content":"0\n166374059\n207967574\n610038216\n177927813\n630578223\n902091444\n412046453\n481340945\n404612686"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}