{"problem":{"name":"1D Reversi Builder","description":{"content":"Kuro and Shiro are playing with a board composed of $n$ squares lining up in a row. The squares are numbered $1$ to $n$ from left to right, and Square $s$ has a mark on it. First, for each square, Kur","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc109_e"},"statements":[{"statement_type":"Markdown","content":"Kuro and Shiro are playing with a board composed of $n$ squares lining up in a row. The squares are numbered $1$ to $n$ from left to right, and Square $s$ has a mark on it.\nFirst, for each square, Kuro paints it black or white with equal probability, independently from other squares. Then, he puts on Square $s$ a stone of the same color as the square.\nKuro and Shiro will play a game using this board and infinitely many black stones and white stones. In this game, Kuro and Shiro alternately put a stone as follows, with Kuro going first:\n\n1.  Choose an empty square adjacent to a square with a stone on it. Let us say Square $i$ is chosen.\n2.  Put on Square $i$ a stone of the same color as the square.\n3.  If there are squares other than Square $i$ that contain a stone of the same color as the stone just placed, among such squares, let Square $j$ be the one nearest to Square $i$. Change the color of every stone between Square $i$ and Square $j$ to the color of Square $i$.\n\nThe game ends when the board has no empty square.\nKuro plays optimally to maximize the number of black stones at the end of the game, while Shiro plays optimally to maximize the number of white stones at the end of the game.\nFor each of the cases $s=1,\\dots,n$, find the expected value, modulo $998244353$, of the number of black stones at the end of the game.\n\n## Constraints\n\n*   $1 \\leq n \\leq 2\\times 10^5$\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$n$\n\n[samples]\n\n## Notes\n\nWhen the expected value in question is represented as an irreducible fraction $p/q$, there uniquely exists an integer $r$ such that $rq=p ~(\\text{mod } 998244353)$ and $0 \\leq r \\lt 998244353$, which we ask you to find.","is_translate":false,"language":"English"}],"meta":{"iden":"arc109_e","tags":[],"sample_group":[["3","499122178\n499122178\n499122178\n\nLet us use `b` to represent a black square and `w` to represent a white square. There are eight possible boards: `www`, `wwb`, `wbw`, `wbb`, `bww`, `bwb`, `bbw`, and `bbb`, which are chosen with equal probability.\nFor each of these boards, there will be $0$, $1$, $0$, $2$, $1$, $3$, $2$, and $3$ black stones at the end of the game, respectively, regardless of the value of $s$. Thus, the expected number of stones is $(0+1+0+2+1+3+2+3)/8 = 3/2$, and the answer is $r = 499122178$, which satisfies $2r = 3 ~(\\text{mod } 998244353)$ and $0 \\leq r \\lt 998244353$."],["10","5\n5\n992395270\n953401350\n735035398\n735035398\n953401350\n992395270\n5\n5"],["19","499122186\n499122186\n499110762\n499034602\n498608106\n496414698\n485691370\n434999274\n201035754\n138645483\n201035754\n434999274\n485691370\n496414698\n498608106\n499034602\n499110762\n499122186\n499122186"]],"created_at":"2026-03-03 11:01:13"}}