Problem Description

You are performing a show in a circus.

There is a number with initial value $x_0$. Perform $K$ operations. In the $i$-th operation, pick a number $x$ uniformly at random from $[0, 2^n)$. With probability $p$, $x_i = x_{i - 1} \operatorname{or} x$; with probability $1 - p$, $x_i = x_{i - 1} \operatorname{and} x$.

The weight of one plan is $\sum_{i=1}^K c_{x_i}$. For each $i \in [0, 2^n)$, compute, among all plans with $x_K = i$, the sum of (weight $\times$ probability), taken modulo $998244353$.

Input Format

The first line contains four integers $n, p', K, x_0$. Here $p'$ is the value of $p$ modulo $998244353$.

The second line contains $2^n$ integers. The $i$-th integer denotes $c_{i - 1}$.

Output Format

Output one line with $2^n$ integers separated by spaces. The $i$-th integer denotes, among all plans with $x_K = i - 1$, the sum of (weight $\times$ probability), taken modulo $998244353$.

2 499122177 2 1
1 1 1 1

374341633 374341633 873463809 374341633

2 332748118 10 0
1 2 4 8

178690412 406663623 594339846 223292982

Hint

For $20\%$ of the testdata, $K \le 20$.

For $40\%$ of the testdata, $K \le 10^3$.

For another $10\%$ of the testdata, $n = 1$.

For another $10\%$ of the testdata, $n \le 8$.

For another $10\%$ of the testdata, $p' = 499122177$.

For another $10\%$ of the testdata, $c_i = 1$.

For $100\%$ of the testdata, $0 \le n \le 17$, $1 \le K \le 10^9$, $0 \le x_0 < 2^n$, $0 \le p', c_i < 998244353$.

Translated by ChatGPT 5