该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

希蒙的异或运算

题目背景

异或运算真的太有趣了，希蒙沉迷其中无法自拔，但是最近他遇到了一个很困难的问题，他自己无法解决了，你能帮帮他吗？

题目描述

给定一个序列$a_i$，求下述式子的值：

$\sum_{1<=l_1<=r_1<l_2<=r_2<l_3<=r_3<=n}XOR(l_1,r_1)\times XOR(l_2,r_2) \times XOR(l_3,r_3)$

其中$XOR(l,r)=a_l\oplus a_{l+1}\oplus\cdots\oplus a_{r_1}\oplus a_r$。

由于这个值可能很大，你只需要输出$MOD\space998244353$意义下的值即可。

输入格式

第一行一个整数$n$，表示给定的序列长度。

第二行$n$个整数$a_i$，表示给定的序列。

输出格式

你一共需要输出一个整数，表示上述式子的值，请注意这是在$MOD\space998244353$意义下的值。

样例 #1

样例输入 #1

3
1 2 3

样例输出 #1

6

样例 #2

样例输入 #2

4
1 1 1 0

样例输出 #2

2

提示

数据范围：

对于10%的数据，我们保证$1<=n<=10$。

对于100%的数据，我们保证$1<=n<=2\times10^5,0<=a_i<=10^9$。