配点 : $700$ 点

問題文

黒石さんと白石さんは、一列に並んだ $n$ 個のマスからなる盤面を使って遊んでいます。 マスにはそれぞれ $1$ から $n$ の整数が順番に振られていて、マス $s$ に印がつけられています。

まず、黒石さんは、各マスについて独立に、黒か白を等確率で選んで塗ります。その後、マス $s$ にマスの色と同じ色の石を置きます。

黒石さんと白石さんは、この盤面と無限個の黒い石と白い石を使ったゲームをします。このゲームでは、黒石さんから始めて、黒石さんと白石さんが交互に次の手順で石を置いていきます。

1. 石が置かれているマスと隣接している空きマスをひとつ選ぶ。マス $i$ を選んだとする。
2. マス $i$ に、マスと同じ色の石をおく。
3. 置いた石と同じ色の石がマス $i$ 以外に置かれているとき、そのうちマス $i$ に最も近い石と、マス $i$ の間にあるすべての石の色をマス $i$ の色に変更する

空きマスが存在しなくなったときにゲームが終了します。

黒石さんはゲーム終了時の黒い石の個数を最大化するために最適な行動をし、白石さんはゲーム終了時の白い石の個数を最大化するために最適な行動をします。

$s=1,\dots,n$ それぞれの場合について、ゲーム終了時の黒い石の個数の期待値を $\text{mod }998244353$ で求めてください。

注意

求める期待値が既約分数 $p/q$ で表されるとき、$rq\equiv p \sim (\text{mod } 998244353)$ かつ $0 \leq r \lt 998244353$ を満たす整数 $r$ がこの問題の制約のもとで一意に定まります。この $r$ が求める値です。

制約

• $1 \leq n \leq 2\times 10^5$

入力

入力は以下の形式で標準入力から与えられる。

$n$

出力

$n$ 個の値を出力せよ。 $i$ 個目には、$s=i$ としたときのゲーム終了時の黒い石の個数の期待値を $\text{mod }998244353$ で出力せよ。

3

499122178
499122178
499122178

黒マスを b で、白マスを w で表すことにします。 盤面として、www, wwb, wbw, wbb, bww, bwb, bbw, bbb の $8$ 通りがあり、これらから等確率に $1$ つが選ばれます。

$s$ によらず、それぞれの盤面について、ゲーム終了時の黒い石の個数は $0,1,0,2,1,3,2,3$ となります。 よって、期待値は $(0+1+0+2+1+3+2+3)/8 = 3/2$ となるため、答えは $2r \equiv 3 \sim (\text{mod } 998244353)$ かつ $0 \leq r \lt 998244353$ を満たす $r = 499122178$ となります。

10

5
5
992395270
953401350
735035398
735035398
953401350
992395270
5
5

19

499122186
499122186
499110762
499034602
498608106
496414698
485691370
434999274
201035754
138645483
201035754
434999274
485691370
496414698
498608106
499034602
499110762
499122186
499122186