Problem Description

Given a set power series $F(x)$ and a polynomial $G(x)$, it is guaranteed that $[x^{\varnothing}]F(x)=0$. Define the multiplication of $x$ as subset convolution. You need to compute, for every $S\subseteq\{1,2,\cdots,n\}$, the value of $[x^S]G(F(x))$ modulo $998244353$.

If you still do not understand the statement, you can read the hint section at the end.

Input Format

The first line contains a positive integer $n$.

The next line contains $2^n$ non-negative integers. The $i$-th integer denotes $[x^S]F(x)$, where $a\in S$ if and only if, in the binary representation of $(i-1)$, the $a$-th bit (from low to high) is $1$.

The next line contains $n+1$ non-negative integers. The $i$-th integer denotes $[x^{i-1}]G(x)$.

Output Format

Output one line containing $2^n$ non-negative integers. The $i$-th integer denotes $[x^S]G(F(x))$ modulo $998244353$, where $a\in S$ if and only if, in the binary representation of $(i-1)$, the $a$-th bit (from low to high) is $1$.

2
0 1 2 3
2 1 1

2 1 2 7

4
0 8 3 2 7 3 9 0 0 1 8 2 3 7 0 2
1 0 4 8 2

1 0 0 192 0 448 168 8824 0 0 0 536 0 248 520 26560 

Hint

Constraints

For all testdata, it is guaranteed that $1\le n\le 20$, and $[x^S]F(x),[x^n]G(x)\in[0,998244353)\cap\mathbb Z$.

This problem has $20$ test points. For the $i$-th test point, $n=i$.

Hint

Suppose $F(x)=\displaystyle \sum_S f_Sx^S$, then $[x^S]F(x)=f_S$.

In this problem, the multiplication of $x$ is defined as subset convolution, i.e.:

$$x^S\cdot x^T=\begin{cases}0&S\cap T\neq\varnothing\\x^{S\cup T}&\text{otherwise}\end{cases}$$

Please pay attention to the efficiency differences caused by contiguous memory access.

Translated by ChatGPT 5