题目背景

カラノワレモノ - ヒトリエ

咲きたいな　笑いたいなあ

好想綻放啊　好想大笑啊

题目描述

定义 $\ominus$ 是一种二进制上的位运算，它每一位的运算表如下：

$x$	$y$	$x\ominus y$
$0$	$0$	$0$
	$1$
$1$	$0$	$1$
	$1$	$0$

这个运算同时是二进制不退位减法。

现在你有一个无序的多重集 $S$。你可以进行若干次操作。若 $S$ 的大小不少于 $2$，则你可以选择 $S$ 中任意两个数，记这两个数是 $x,y$。然后将这两个数合并成 $x\ominus y$ 或 $y\ominus x$。

最后请你将 $S$ 合并至剩下一个数，试求出这个数的最大值。

你有一个长度为 $n$ 的非负整数序列 $a_1, \ldots, a_n$。定义 $f(l,r)$ 表示将序列 $a$ 中 $[l,r]$ 这个区间内的数作为多重集 $S$ 中的元素时上述问题的答案。

试求出

$$\sum_{i=1}^n \sum_{j=i}^n f(i,j)$$

对 $998244353$ 取模后的值。

输入格式

第一行，一个正整数 $n$。

第二行，$n$ 个非负整数 $a_1, \ldots, a_n$。

输出格式

输出一行一个非负整数，表示答案对 $998244353$ 取模后的值。

3
1 2 3

11

提示

【样例解释 #1】

考虑 $f(1,3)$ 的计算过程：

多重集 $S=\{1,2,3\}$。

先将 $1$ 和 $2$ 合并成 $1\ominus 2=1$。

再将 $3$ 和 $1$ 合并成 $3\ominus 1=2$。

可以证明，你无法得到 $>2$ 的最终结果。所以 $f(1,3)=2$。

类似的计算得到：

$f(1,1)=1$，$f(1,2)=2$，$f(2,2)=2$，$f(2,3)=1$，$f(3,3)=3$。

总和为 $11$。

【样例 #2】

见选手目录下的 $\textbf{\textit{heal/heal2.in}}$ 与 $\textbf{\textit{heal/heal2.ans}}$。

该样例满足测试点 $1\sim 5$ 的约束条件。

【样例 #3】

见选手目录下的 $\textbf{\textit{heal/heal3.in}}$ 与 $\textbf{\textit{heal/heal3.ans}}$。

该样例满足测试点 $6\sim 8$ 的约束条件。

【样例 #4】

见选手目录下的 $\textbf{\textit{heal/heal4.in}}$ 与 $\textbf{\textit{heal/heal4.ans}}$。

该样例满足测试点 $9\sim 11$ 的约束条件。

【样例 #5】

见选手目录下的 $\textbf{\textit{heal/heal5.in}}$ 与 $\textbf{\textit{heal/heal5.ans}}$。

该样例满足测试点 $14\sim 18$ 的约束条件。

【样例 #6】

见选手目录下的 $\textbf{\textit{heal/heal6.in}}$ 与 $\textbf{\textit{heal/heal6.ans}}$。

该样例满足测试点 $19$ 的约束条件。

【样例 #7】

见选手目录下的 $\textbf{\textit{heal/heal7.in}}$ 与 $\textbf{\textit{heal/heal7.ans}}$。

该样例满足测试点 $23\sim 25$ 的约束条件。

【数据范围】

本题共 $25$ 个测试点，每个 $4$ 分。

对于所有测试数据，保证：

• $1\le n\le 2\times 10^5$；
• $0\le a_i < 2^{25}$。

::cute-table{tuack}

测试点编号	$n\le$	特殊性质
$1\sim 5$	$4$	B
$6\sim 8$	$10^3$	AB
$9\sim 11$	^	B
$12, 13$	$2\times 10^4$	AB
$14\sim 18$	^	无
$19$	$10^5$	AB
$20\sim 22$	^	无
$23\sim 25$	$2\times 10^5$	^

特殊性质 A：对于所有 $1 \le i \le n$ 均存在非负整数 $k$ 使得 $a_i=2^k$。
特殊性质 B：保证 $a$ 序列中的每个元素都从所有满足条件的元素中等概率随机选取。