题目背景

Lately, I've been hearing the cries of the angels when I close my eyes

Remember?

题目描述

Technic_Angel 想用粒子来制作一支美丽的水晶。Pathselector 告诉她，一支水晶由 $m$ 簇粒子合成，其中每一簇粒子都有美丽度（一个小于 $2^w$ 的非负整数，其中 $w$ 为给定正整数），而一支水晶的美丽度就是合成它的所有粒子的美丽度的异或和。

Technic_Angel 有许多粒子：对于每一个 $i\in[0,2^w)\cap\Z$，她都有恰好 $v_i$ 簇美丽度为 $i$ 的粒子。现在 Technic_Angel 想要知道，有多少种方案能够合成一支美丽度为 $k$ 的水晶呢？（两种方案不同，当且仅当有一簇粒子在一种方案中被使用而在另一种方案中没有；所有粒子都互不相同）可惜她并不会这个问题，于是她找到了擅长 OI 的你。

在你花 $0.01\mu s$ 切掉这道题后，异常惊喜的 Technic_Angel 想要让你对所有 $k\in[0,2^w)\cap\Z$ 都解决上面的问题。但由于答案过于巨大，她只要求你告诉她对于所有的 $i$，$((i+1)f(i))\bmod998244353$ 的异或和，其中 $f(i)$ 代表合成一支美丽度为 $i$ 的水晶的方案数。即

$$(f(0)\bmod P)\otimes(2f(1)\bmod P)\otimes\cdots\otimes(2^wf(2^w-1)\bmod P) $$

其中 $P=998244353$，$\otimes$ 代表异或。注意是取模后的异或和而非异或后再取模。

输入格式

第一行两个正整数 $m,w$，分别代表合成水晶所需的粒子数目以及问题中的参数。

第二行 $2^w$ 个正整数，第 $i$ 个整数代表 $v_{i-1}$。

输出格式

一行一个整数，代表 $((i+1)f(i))\bmod 998244353$ 的异或和。

2 2
0 1 1 1

5

3 3
2 0 1 7 1 2 0 1

320

5 3
2 0 2 1 0 4 2 3

1482

提示

样例解释

样例一：Technic_Angel 共有三簇粒子，美丽度分别为 $1,2,3$。用序列表示选出的粒子的美丽度的话，没有合成美丽度为 $0$ 的水晶的方案，而为 $1$、为 $2$ 和为 $3$ 的方案各有一种（分别是 $[2,3]$、$[1,3]$ 和 $[1,2]$），于是答案为 $0\otimes2\otimes3\otimes4=5$。

数据范围

令 $n=\sum v_i$。对于全部数据，有 $0\le n,v_i<998244353$，$1\le m\le\min\{n,10^6\}$，$1\le w\le 20$。

子任务	$n,m,w$	特殊性质	分值
1	$m=1$	$A$	5
2	$n\le200,w\le8$		10
3	$m=2$		20
4	无	$A,B$	25
5		$A$	38
6	$m\le 60000,w\le16$	无	2

特殊性质 $A$：$n\le10^6$。

特殊性质 $B$：$2^w\cdot m\le 6\cdot 10^7$。