配点 : $1600$ 点

問題文

すぬけくんはある乱数生成器を手に入れました。 この乱数生成器は、$0$ 以上 $2^N-1$ 以下の整数を生成します。 それぞれの整数を生成する確率は、整数列 $A_0,A_1,\cdots,A_{2^N-1}$ によって表され、 整数 $i$ ($0 \leq i \leq 2^N-1$) が生成される確率は $A_i / S$ です。 ただしここで $S = \sum_{i=0}^{2^N-1} A_i$ とします。 また、乱数生成は毎回独立に行われます。

すぬけくんは整数 $X$ を持っています。 今、$X=0$ です。 すぬけくんは、次の操作を好きなだけ行うことが出来ます。

• 乱数生成器で一つの整数 $v$ を生成する。そして、$X$ を $X \oplus v$ で置き換える。 ただしここで、$\oplus$ はビットごとの排他的論理和を表す。

それぞれの整数 $i$ ($0 \leq i \leq 2^N-1$) について、$X$ を $i$ にするために必要な操作の回数の期待値を求めてください。 ただし、期待値は mod $998244353$ で出力してください。 より正確には、期待値が既約分数 $P/Q$ で表されるとき、 $R \times Q \equiv P \mod 998244353,\ 0 \leq R < 998244353$ を満たす整数 $R$ が一意に定まるので、その $R$ を出力してください。

なお、すべての $i$ について、$X$ を $i$ にするために必要な操作の回数の期待値が有理数として存在し、 さらに mod $998244353$ での整数表現が定義できることが問題の制約から証明できます。

制約

• $1 \leq N \leq 18$
• $1 \leq A_i \leq 1000$
• 入力される値はすべて整数である。

入力

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

$N$

$A_0$ $A_1$ $\cdots$ $A_{2^N-1}$

出力

$2^N$ 行出力せよ。 $i+1$ 行目 ($0 \leq i \leq 2^N-1$) には、$X$ を $i$ にするために必要な操作の回数の期待値を mod $998244353$ で出力せよ。

2
1 1 1 1

0
4
4
4

$0$ 回操作をした段階で $X=0$ なので、$X$ を $0$ にするのに必要な操作回数の期待値は $0$ です。

また、どの状態から操作しても、操作後の $X$ の値はそれぞれ $1/4$ の確率で $0,1,2,3$ になります。 よって、$X$ を $1,2,3$ にするのに必要な操作回数の期待値はいずれも $4$ です。

2
1 2 1 2

0
499122180
4
499122180

$X$ を $0,1,2,3$ にするのに必要な操作回数の期待値は、それぞれ $0,7/2,4,7/2$ です。

4
337 780 799 10 796 875 331 223 941 67 148 483 390 565 116 355

0
468683018
635850749
96019779
657074071
24757563
745107950
665159588
551278361
143136064
557841197
185790407
988018173
247117461
129098626
789682908