Во время археологической экспедиции на Луне исследователи изучают цепочку из n секторов раскопок, расположенных вдоль древнего подповерхностного тоннеля. В каждом секторе найден артефакт, для которого записано некоторое целое число a_i.

Для любого непрерывного участка секторов от l до r включительно археологи определяют его энергетическую ценность так:

• сначала вычисляется побитовое XOR всех чисел на этом участке;
• затем полученное значение умножается на длину участка, то есть на r - l + 1.

Формально, ценность участка [l, r] равна

\[ (a_l \oplus a_{l+1} \oplus \dots \oplus a_r) \cdot (r - l + 1). \]

Ваша задача — найти сумму энергетических ценностей по всем непрерывным участкам массива.

Формат входных данных

В первой строке записано одно целое число n — количество секторов раскопок.

Во второй строке записаны n целых чисел a_1, a_2, ..., a_n — значения, связанные с найденными артефактами.

Формат выходных данных

Выведите одно целое число — сумму энергетических ценностей всех непрерывных участков по модулю 998244353.

Ограничения

• 1 ≤ n ≤ 3 · 10^5
• 0 ≤ a_i < 2^30

Пример 1

Входные данные

3
1 3 2

Выходные данные

12

Пример 2

Входные данные

1
5

Выходные данные

5

Пример 3

Входные данные

4
1 2 3 4

Выходные данные

63

Пояснение к первому примеру

Рассмотрим все непрерывные участки:

• [1, 1]: 1 · 1 = 1
• [2, 2]: 3 · 1 = 3
• [3, 3]: 2 · 1 = 2
• [1, 2]: (1 ⊕ 3) · 2 = 2 · 2 = 4
• [2, 3]: (3 ⊕ 2) · 2 = 1 · 2 = 2
• [1, 3]: (1 ⊕ 3 ⊕ 2) · 3 = 0 · 3 = 0

Сумма равна 1 + 3 + 2 + 4 + 2 + 0 = 12.

Примечание

Под непрерывным участком понимается последовательность элементов массива с индексами от l до r, где 1 ≤ l ≤ r ≤ n. Побитовая операция XOR обозначается символом ⊕.