回响（echo）

• 输入：echo.in
• 输出：echo.out
• 时间限制：2 s
• 内存限制：256 MB

题目描述

一首乐曲结束后，最后一个音符的回响仍未消散。小 R 正在为音游设计一种回放特效：不同片段会产生不同的回响，而片段越长，回响也会被进一步放大。

一首乐曲被划分为连续的 $n$ 个节拍，第 $i$ 个节拍有一个非负整数特征值 $a_i$。

选择两个整数 $l,r$，满足 $1 \le l \le r \le n$，就能得到由第 $l$ 个至第 $r$ 个节拍组成的连续片段。该片段的特征值定义为其中所有节拍特征值的按位异或结果：

$a_l \oplus a_{l+1} \oplus \cdots \oplus a_r.$

片段的回响值定义为其特征值乘以片段长度，即：

$(a_l \oplus a_{l+1} \oplus \cdots \oplus a_r) \times (r-l+1).$

请计算所有连续片段的回响值之和，并输出它对 $998244353$ 取模后的结果。两个片段只要左端点或右端点不同，就视为不同片段。

其中，$\oplus$ 表示按位异或：将两个数写成二进制，在每一位上，两个数字不同时结果为 $1$，相同时结果为 $0$。例如 $3 \oplus 5 = 6$。在 C++ 中可使用运算符 ^ 进行按位异或运算。

输入格式

从文件 echo.in 中读入数据。

第一行包含一个正整数 $n$，表示乐曲的节拍数量。

第二行包含 $n$ 个非负整数 $a_1,a_2,\cdots,a_n$，依次表示每个节拍的特征值。

输出格式

输出到文件 echo.out 中。

输出一行一个整数，表示所有连续片段的回响值之和对 $998244353$ 取模后的结果。

3
1 3 2

12

样例1解释

共有六个连续片段：

因此答案为 $1+4+0+3+2+2=12$。

4
1 0 1 1

11

数据范围

对于所有数据，$1 \le n \le 3 \times 10^5$，$0 \le a_i \le 10^9$。每个测试点 $5$ 分。

特殊性质 A：对于所有 $1 \le i \le n$，均有 $a_i \in \{0,1\}$。