집합 멱급수의 거듭제곱 사영

정수 $M$, $N$변수 다항식 $\displaystyle s(x _ 0, x _ 1, \dots, x _ {N - 1}) = \sum _ {i = 0} ^ {2 ^ N - 1} a _ i \prod _ {k = 0} ^ {N - 1} x _ k ^ {i _ k} \in \mathbb{F} _ {998244353} \lbrack x _ 0, x _ 1, \dots, x _ {N - 1} \rbrack$, 그리고 $\mathbb{F} _ {998244353}$의 원소로 이루어진 수열 $(w _ 0, \ldots, w _ {2 ^ N - 1})$이 주어진다. 여기서 $i$을 이진수로 나타냈을 때 $i_k$는 $2 ^ k$ 자리의 수를 나타낸다.

각 $m=0,1,\ldots,M-1$에 대해, $s(x _ 0, x _ 1, \dots, x _ {N - 1})^m \equiv \sum _ {i = 0} ^ {2 ^ N - 1} b _ i \prod _ {k = 0} ^ {N - 1} x _ k ^ {i _ k} \pmod{(x _ 0 ^ 2, x _ 1 ^ 2, \dots, x _ {N - 1} ^ 2)}$로 정의되는 $b_i$에 대하여 $\sum _ {i=0} ^ {2 ^ N - 1} w_ib_i$을 계산한다.

제약 조건

• $0 \leq N \leq 20$
• $0 \leq M \leq 100000$
• $0 \leq a_i, w_i \lt 998244353$

$N$ $M$
$a _ 0$ $a _ 1$ $\cdots$ $a _ {2^N-1}$
$w _ 0$ $w _ 1$ $\cdots$ $w _ {2^N-1}$

$\mathrm{ans}_0$ $\mathrm{ans}_1$ $\cdots$ $\mathrm{ans}_{M-1}$