Problem Description

Given a sequence $a_1,a_2,\cdots,a_n$, define $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)$, where $\oplus$ denotes the bitwise XOR operation, and $\vee$ denotes the bitwise OR operation.

You need to compute the variance $v$ of all values $f(l,r)$ that satisfy $1\le l \le r \le n$. To avoid precision errors, and since the answer may be very large, output $(v\times \frac{n^2\times (n+1)^2}{4}) \kern{3pt}\mathrm {mod}\kern{3pt} 998244353$.

Note: Do not take modulo during the computation. Only take modulo for the final result.

Input Format

The first line contains a positive integer $n$.

The second line contains $n$ positive integers $a_1,a_2,\cdots,a_n$.

Output Format

Output an integer $(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

Hint

Definition of variance: for $n$ numbers $a_1,a_2,\cdots,a_n$, their variance is:

where $\bar{a}$ is the average of $a_1,a_2,\cdots,a_n$, that is, $\dfrac {1} {n} \displaystyle\sum\limits_{i=1}^n a_i$.

For $10\%$ of the testdata, $n \le 50$.

For $30\%$ of the testdata, $n \le 5000$.

For another $20\%$ of the testdata, $a_i \le 100$.

For $100\%$ of the testdata, $1\le n\le 10^5,1\le a_i < 2^{31}$.

Translated by ChatGPT 5