$n$ 个人围成一个环，依次标号为 $1,2,\dots,n$，每个人都有一口锅。

第 $i$ 个人可以选择把自己的锅甩给除了自己以外的其余 $n-1$ 个人中任意一个，也可以选择不甩锅。根据甩锅第一定律，甩锅行为不能成环，即不能存在序列 $v_1, v_2, \dots, v_k, v_{k+1}$ 满足 $v_{k+1} = v_1$，对于每个 $1 \le i \le k$，第 $v_i$ 个人把锅甩给了第 $v_{i+1}$ 个人。由于这样子总存在至少一个无法被解决的锅，这样的甩锅方案显然是一个非法的甩锅方案。

我们用咕值来量化甩锅行为对任务完成效率的影响。研究表明一次甩锅行为的咕值只与甩锅者与被甩锅者在环上的相对位置有关，具体的，如果第 $i$ 个人决定甩锅，且将锅甩给了第 $j$ 个人，他的咕值为 $\omega_{(i-j+n)\bmod n}$，其中 $\omega_k$ 为一个既定参数。如果第 $i$ 个人决定不甩锅，则他的咕值为 $1$。

我们定义一个合法的甩锅方案的咕值为每一个人的咕值的乘积，求所有可能的甩锅方案的咕值之和对 $998\,244\,353$ 取模后的结果。两个甩锅方案被认为是不同的，当且仅当存在某个人的选择不同（即是否选择了甩锅、选择甩给了谁）。

输入格式

从标准输入中读入数据。

输入数据共包含两行，第一行为一个正整数 $m$，题目描述中的 $n=2^m$。

接下来一行 $n-1$ 个用空格分隔的整数 $\omega_1, \omega_2, \dots, \omega_{n-1}$，保证 $\omega_i \in [0, 998\,244\,353)$。

输出格式

输出到标准输出中。

输出一行一个整数表示答案对 $998\,244\,353$ 取模后的结果。

样例数据

样例输入

3
1 2 3 4 5 6 7

样例输出

148656674

数据范围

对于 $20\%$ 的数据，$m \le 3$；

对于 $40\%$ 的数据，$m \le 8$；

对于 $60\%$ 的数据，$m \le 12$；

对于另外 $20\%$ 的数据，$\omega_k$ 全相等；

对于 $100\%$ 的数据，$2 \le m \le 20$，$\omega_k \in [0, 998\,244\,353)$。