题目描述

skip2004 和 ignore2004 是好朋友，他们经常在一起玩游戏。

一天，他们在玩一个合作型游戏，这个游戏的规则是这样的：

在他们面前，有一个 $n$ 位二进制数 $\boldsymbol x$，初始时它等于 $\left( b_{n-1} b_{n-2} \ldots b_1 b_0 \right)_2$，然后他们可以进行若干轮操作，每轮操作规则如下：

• 首先，skip2004 要选择一个 $n$ 位二进制数 $\boldsymbol y = \left( c_{n-1} c_{n-2} \ldots c_1 c_0 \right)_2$。
• 接着，ignore2004 要选择一个为 $\mathbin \&$ 或 $\mid$ 的运算符，记作 $\circledast$。
• 然后，令 $\boldsymbol z = \begin{cases} \left( c_{n-1} c_{n-2} \ldots c_1 c_0 \right)_2 & \circledast = \mathbin \& \\[0.4em] \left( \overline {c_{n-1} c_{n-2} \ldots c_1 c_0} \right)_2 & \circledast = {|} \end{cases}$，其中 $\bar {c_i} = 1 - c_i$ 表示按位取反。
• 最后，令 $\boldsymbol x \gets \boldsymbol x \circledast \boldsymbol z$。

(ps: $\mathbin \&$ 表示按位与运算符，$\mid$ 表示按位或运算符)

游戏的目标是，再经过若干 ($\geq 1$) 轮操作后，使 $\boldsymbol x$ 再次回到 $\left( b_{n-1} b_{n-2} \ldots b_1 b_0 \right)_2$ (即除去初始状态后首次达到 $\left( b_{n-1} b_{n-2} \ldots b_1 b_0 \right)_2$)。

为了增强游戏的趣味性，skip2004 和 ignore2004 决定随机决定 $\boldsymbol y$ 和 $\circledast$。具体地：

• 在 skip2004 随机时，对于 $\forall i \in \left[ 0, n - 1 \right]$，$c_i$ 均有独立的 $p_i$ 的概率为 $1$，$1 - p_i$ 的概率为 $0$。
• 在 ignore2004 随机时，$\circledast$ 有独立的 $q$ 的概率为 $\mathbin \&$，$1 - q$ 的概率为 $\mid$。

他们想知道，按照这种随机策略，游戏经过轮数 (即 $\boldsymbol x$ 从 $\left( b_{n-1} b_{n-2} \ldots b_1 b_0 \right)_2$ 再次回到 $\left( b_{n-1} b_{n-2} \ldots b_1 b_0 \right)_2$) 的期望。

由于他们不知道最初的二进制数 $\left( b_{n-1} b_{n-2} \ldots b_1 b_0 \right)_2$，因此你需要对所有 $2^n$ 种可能的 $\left( b_{n-1} b_{n-2} \ldots b_1 b_0 \right)_2$ 都回答这个问题。

输入格式

第一行包含两个正整数 $n, q^\ast$，分别表示二进制数的位数和 ignore2004 随机的参数。具体地，有 $q = \dfrac {q^\ast} {998244354}$。

第二行包含 $n$ 个正整数 $p_0^\ast, p_1^\ast, \ldots, p_{n-1}^\ast$ 描述 skip2004 随机的参数。具体地，有 $p_i = \dfrac {p_i^\ast} {998244354}$。

输出格式

记 $\left( b_{n-1} b_{n-2} \ldots b_1 b_0 \right)_2$ 的答案 (期望) 为 $E_j$ (其中 $j$ 为 $\left( b_{n-1} b_{n-2} \ldots b_1 b_0 \right)_2$ 的十进制表示)，用 $e_j$ 表示 $E_j$ 在模 $998244353$ 意义下的值。

则输出一行一个整数，表示

$$\bigoplus_{j=0}^{2^n-1} \left( 2004^j \cdot e_j \bmod 998244353 \right) $$

其中 $\oplus$ 表示按位异或运算符。

(ps: 对于一个分母不为 $998244353$ 的倍数的 (最简) 有理数 $\dfrac pq$，它在模 $998244353$ 意义下的值被定义为满足 $q \cdot r \equiv p \pmod {998244353}$ 且 $r \in \left[ 0, 998244352 \right]$ 的唯一整数 $r$)

1 499122177
499122177

4010

4 230167959
49 38 15 98

675282672

数据范围与提示

对于所有的测试点，均满足 $1 \leq n \leq 20; 2 \leq p_i, q \leq 998244352$，且数据以某种方式随机，以确保你在计算过程中不必考虑计算 $0$ 的逆元的情况。

具体的子任务的数据规模见下表：

子任务	附加限制	分值
1	$n \leq 5$	$22$
2	$p_i = q = 499122177$	$22$
3	$n \leq 8$	$22$
4	无特殊限制	$34$