题目描述

给定序列 $a_1,a_2,\cdots,a_n$，定义 $f(l,r)=(a_l\oplus a_{l+1}\oplus \cdots \oplus a_r)+(a_l\vee a_{l+1}\vee \cdots \vee a_r)$，其中 $\oplus$ 表示 按位异或 运算，$\vee$ 表示 按位或 运算。

你需要求出所有满足 $1\le l \le r \le n$ 的 $f(l,r)$ 的方差 $v$。为避免精度误差，以及答案可能很大，请输出 $(v\times \frac{n^2\times (n+1)^2}{4}) \kern{3pt}\mathrm {mod}\kern{3pt} 998244353$。

注意：运算过程中不取模，仅将结果取模。

输入格式

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

第二行 $n$ 个正整数 $a_1,a_2,\cdots,a_n$。

输出格式

输出一个整数 $(v\times \frac{n^2\times (n+1)^2}{4}) \kern{3pt}\mathrm {mod}\kern{3pt} 998244353$。

3
2 1 3

80

4
4 1 3 2

1244

5
1 2 3 2 1

444

提示

方差的定义：对于 $n$ 个数 $a_1,a_2,\cdots,a_n$，它们的方差是：

其中 $\bar{a}$ 为 $a_1,a_2,\cdots,a_n$ 的平均数，即 $\dfrac {1} {n} \displaystyle\sum\limits_{i=1}^n a_i$。

对于 $10\%$ 的数据，$n \le 50$。

对于 $30\%$ 的数据，$n \le 5000$。

对于另 $20\%$ 的数据，$a_i \le 100$。

对于 $100\%$ 的数据，$1\le n\le 10^5,1\le a_i < 2^{31}$。