Subset Convolution Logarithm

We are given a set power series \(F(x)=\sum_{S\subseteq\{1,2,\dots,n\}} f_S x^S\) with the constant term \([x^{\varnothing}]F(x)=1\). The multiplication for the formal variable \(x\) is defined via subset convolution: for two series \(A(x)=\sum_{S} a_S x^S\) and \(B(x)=\sum_{S} b_S x^S\) we define

[ (A*B)(S)=\sum_{T\subseteq S} a_T,b_{S\setminus T},]

so that the exponential of a series \(G(x)=\sum_S g_S x^S\) is defined as

[ e^{G(x)}=\sum_{k\ge 0} \frac{G(x)^{*k}}{k!}, \quad \text{with } G(x)^{*0}=1. ]

It can be shown that there exists a unique series \(G(x)\) satisfying

[ e^{G(x)}=F(x). ]

Your task is to compute \([x^S]G(x)\) modulo \(998244353\) for every subset \(S\subseteq\{1,2,\dots,n\}\).

Note: The input describes \(F(x)\) by giving \(f_S\) for every subset \(S\) (ordered by the bitmask representation, with \(S=\varnothing\) corresponding to 0). You are guaranteed that \(f_{\varnothing}=1\) so that \(\log F(x)\) is defined and \(G(\varnothing)=0\).

inputFormat

The first line contains an integer \(n\) (size of the base set). The second line contains \(2^n\) integers \(f_0, f_1, \dots, f_{2^n-1}\), where the integer corresponding to index \(i\) represents \(f_S\) for the subset \(S\) whose bitmask is \(i\) (with \(f_0 = 1\) corresponding to the empty set).

outputFormat

Output \(2^n\) integers: \(g_0, g_1, \dots, g_{2^n-1}\), where \(g_i=[x^S]G(x)\) for the subset \(S\) corresponding to bitmask \(i\), taken modulo \(998244353\). (Note that \(g_0\) must be 0 since \(G(\varnothing)=\log 1=0\).)

sample

2
1 2 3 4

0 2 3 998244345