Level : Codeforces Div-2 D

You are given an array a containing n non-negative integers.

For every subarray [l, r], define its XOR value as:

f(l, r) = a_l ⊕ a_{l+1} ⊕ ... ⊕ a_r

where ⊕ represents the bitwise XOR operation.

Your task is to compute the following weighted sum over all possible subarrays:

Σ(l=1 to n) Σ(r=l to n) f(l, r) × (r - l + 1)

In other words, the XOR of each subarray is multiplied by the length of that subarray, and all such values are added together.

Since the resulting value can be extremely large, output the answer modulo 998244353.

Input

The first line contains a single integer n — the size of the array.

The second line contains n integers:

a_1, a_2, ..., a_n

representing the elements of the array.

Constraints

• 1 ≤ n ≤ 3 × 10^5
• 0 ≤ a_i ≤ 10^9

Output

Print a single integer — the required weighted sum of XOR values over all subarrays, taken modulo 998244353.

Examples

Example 1

Input

3
1 3 2

Output

12

Example 2

Input

4
39 68 31 80

Output

1337

Example 3

Input

7
313539461 779847196 221612534 488613315 633203958 394620685 761188160

Output

257421502

Explanation

For the first example, consider every subarray and multiply its XOR value by its length:

• [1] → XOR = 1, contribution = 1 × 1
• [1, 3] → XOR = 2, contribution = 2 × 2
• [1, 3, 2] → XOR = 0, contribution = 0 × 3
• [3] → XOR = 3, contribution = 3 × 1
• [3, 2] → XOR = 1, contribution = 1 × 2
• [2] → XOR = 2, contribution = 2 × 1

Their total is:

1 + 4 + 0 + 3 + 2 + 2 = 12

Hence, the answer is 12.