题目描述

すぬけくんはある乱数生成器を手に入れました。 この乱数生成器は、$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$ での整数表現が定義できることが問題の制約から証明できます。

输入格式

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

$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$ で出力せよ。

题目大意

给定 $n$ 和一个长度为 $2^n$ 的数组 $A$ (从 $0$ 标号).

有一个初始为 $0$ 的变量 $x$ . 不断操作, 每次操作以 $\dfrac {A_i}{\sum_{j=0}^{2^n-1} A_j}$ 的概率将 $x$ 变成 $x\oplus i$ .

对于所有 $i\in[0,2^n)$, 求出 $x$ 第一次变成 $i$ 的期望操作次数.

$n\leqslant 18, 1\leqslant A\leqslant 1000$。

2
1 1 1 1

0
4
4
4

2
1 2 1 2

0
499122180
4
499122180

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

提示

制約

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

Sample Explanation 1

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

Sample Explanation 2

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