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 find the variance \(v\) of all \(f(l, r)\) such that \(1 \le l \le r \le n\). To avoid precision errors and because the answer might be very large, output \((v \times \frac{n^2 \times (n+1)^2}{4}) \mod 998244353\).

Note: Do not take modulo during the computation process, only take modulo of the 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 a single integer \((v \times \frac{n^2 \times (n+1)^2}{4}) \mod 998244353\).

Sample Input and Output

Sample Input #1

3
2 1 3

Sample Output #1

80

Sample Input #2

4
4 1 3 2

Sample Output #2

1244

Sample Input #3

5
1 2 3 2 1

Sample Output #3

444

Notes

The definition of variance: For \(n\) numbers \(a_1, a_2, \cdots, a_n\), their variance is:

\[ \frac{1}{n} \sum_{i=1}^n (a_i - \bar{a})^2 \]

where \(\bar{a}\) is the average of \(a_1, a_2, \cdots, a_n\), i.e., \(\frac{1}{n} \sum_{i=1}^n a_i\).

For \(10\%\) of the data, \(n \le 50\).

For \(30\%\) of the data, \(n \le 5000\).

For another \(20\%\) of the data, \(a_i \le 100\).

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

见题面 Input 部分

见题面 Output 部分