Evan 和 Lyra 都是聪明可爱的孩子，两年前，Evan 开始为一个被称为UOJ的神秘的OI组织工作，在 Evan 与其他小伙伴的努力下，UOJ不仅成了OI界原创比赛的典范，更是因UR这一反人类难度的存在而举世闻名。然而今年，随着 Evan 前往世界彼岸，UOJ一天天减少着他的活力，而就在OI历新年的黎明——NOI的前夕，刚回家不久的Evan听到了清脆的敲门声……

“开门，快递！”

“暗号？”

“3a34be41f8c8796c93b5c9f3b988e0d4”

“收到！”

送走了快递小哥，Evan 拆开包裹，看见一个写着“量子态的巧克力”的小盒子，作为新时代的OI少年，Evan 决定发扬分享的精神，于是他找来 Lyra 一起打开巧克力的盒子。

“砰——”

从量子态坍缩的光芒中回过神来，感受到脚下啫喱状的地板，Evan 叹了一口气——接着突然用把 Lyra 吓了一跳的音量喊了出来：

“竟然把造题的锅塞进巧克力里！！”

而这时，Lyra已经开始观察起了这盒奇特的巧克力，并找到了藏在巧克力盒子里的说明书。

原来，盒子里每个巧克力都有一个味道 $a_i$，Evan 和 Lyra 的舌头上都还没有残留任何味道（用 $0$ 表示），当他们吃下一块巧克力的时候，舌头上的味道 $b$ 便会异或上这个巧克力的美味值，即 $b\leftarrow b\mathtt{\text{xor}}a$.

Evan 和 Lyra 会各自从盒子中拿一些巧克力吃下去（即各自选择一个集合并吃掉集合中的巧克力），两个人不能吃同一块巧克力（即集合不能相交），可以有一个人选择不吃巧克力，但不能两个人都不吃。Evan 和 Lyra 不需要把盒子里的巧克力都吃完，有剩余也是可以的。

最后如果二人舌头上残留着相同的味道，则称两人是心情契合的。

既然量子态有无数种可能性，走出这巧克力迷局的关键就是，求出有多少种方案使得两人是心情契合的，两种方案不同当且仅当 Evan 或 Lyra 选择吃下的巧克力集合不一样。

你只需要输出方案数对 $998244353$ 取模的结果即可。

输入格式

第一行一个正整数 $n$ ，表示巧克力的个数。

第二行 $n$ 个整数 $a_i$ 表示每个巧克力的美味值。

输出格式

输出一行一个整数，表示能使得他们心情契合的吃巧克力的方案数对 $998244353$ 取模的结果。

样例一

input

3
1 2 3

output

8

explanation

无论 Evan 选哪个集合，Lyra 都要选 Evan 的补集。

样例二

input

6
1 2 3 4 5 6

output

80

样例三

见样例数据下载，限制与约定跟第 $7$ 个测试点相同。

样例四

见样例数据下载，限制与约定跟第 $8$ 个测试点相同。

限制与约定

对于全部数据，$1\le n\le {10}^6;0\le a_i\le {10}^6.$

各个测试点限制见下表：

时间限制：$1\mathtt{\text{s}}$

空间限制：$256\mathtt{\text{MB}}$

下载

样例数据下载