题目描述

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

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

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

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

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

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

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

输入格式

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

$n$

输出格式

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

题目大意

有一个长为 $n$ 的表格，将每个格子等概率随机染成黑色或白色。

初始标记第 $x$ 个格子，有两个人进行博弈，每次可以选择标记一个未被标记的格子，满足相邻的某个格子已被标记。设选择的格子颜色为 $c$，然后找到与当前格子最近的颜色为 $c$ 的格子，并将这两个格子之间的一段区间均染成 $c$。

先手想要最大化最终黑色的格子数，后手反之，问最终黑色格子数的期望。

3

499122178
499122178
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

提示

注意

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

制約

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

Sample Explanation 1

黒マスを 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\ ~(\text{mod\ }\ 998244353)$ かつ $0\ \leq\ r\ \lt\ 998244353$ を満たす $r\ =\ 499122178$ となります。