Variance of Subarray Function

Given a sequence of integers \(a_1, a_2, \ldots, a_n\), define the function for a subarray as follows:

\[ f(l,r) = \Bigl( a_l \oplus a_{l+1} \oplus \cdots \oplus a_r \Bigr) + \Bigl( a_l \vee a_{l+1} \vee \cdots \vee a_r \Bigr), \]

where \(\oplus\) denotes the bitwise XOR operation and \(\vee\) denotes the bitwise OR operation.

Your task is to calculate the variance \(v\) of \(f(l, r)\) taken over all subarrays (i.e. for all \(1 \le l \le r \le n\)). Formally, if \(m = \frac{n(n+1)}{2}\) is the total number of subarrays, and \[ E[f] = \frac{1}{m}\sum_{1 \le l \le r \le n} f(l,r), \qquad E[f^2] = \frac{1}{m}\sum_{1 \le l \le r \le n} f(l,r)^2, \] then the variance is defined as \(v = E[f^2] - (E[f])^2\).

You are required to output \[ \left(v \times \frac{n^2 (n+1)^2}{4}\right) \bmod 998244353, \] which, after a short simplification, is equivalent to computing \[ \left(m \times \sum_{l,r} f(l,r)^2 - \Bigl(\sum_{l,r} f(l,r)\Bigr)^2 \right) \bmod 998244353, \] since \(m=\frac{n(n+1)}{2}\).

Note: The arithmetic operations should be carried out exactly without taking any modulo until the final result is computed.

inputFormat

The first line contains a single integer \(n\) (the length of the sequence).
The second line contains \(n\) integers \(a_1, a_2, \ldots, a_n\) separated by spaces.

outputFormat

Output a single integer, the value of \(\left(v \times \frac{n^2 (n+1)^2}{4}\right) \bmod 998244353\).

sample

1
0

0