E. Киа, Кио и Древо жизни
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Разблокировав кристаллический терминал, Киа и Кио обнаружили чертёж забытого сердца королевства — цифрового Древа жизни, посеянного массивом $$$a_1, a_2, \ldots, a_n$$$.

Чтобы восстановить его пульс, им нужно было сплести воедино все возможные воплощения Древа. Для каждого непрерывного отрезка Киа осторожно выбирала индекс $$$i$$$, в котором будет находиться корень. Доверяя её замыслу, Кио бережно сплетал ветви жизни — по такому же принципу рекурсивно создавал левое поддерево из предшествующего отрезка $$$[1, i-1]$$$, а правое поддерево — из последующего отрезка $$$[i+1, n]$$$.

Когда Древо жизни расцветало, его жизненный резонанс $$$f(\text{tree})$$$ определялся его связями. Если разорвать любую из $$$n-1$$$ хрупких ветвей, Древо распадётся на две несвязанные половины, высвободив энергию $$$X+Y$$$, где $$$X$$$ и $$$Y$$$ — результаты применения побитового исключающего ИЛИ ко всем элементам массива, оставшимся в первой и второй половинах соответственно.

Полная мощность Древа $$$f(\text{tree})$$$ равна сумме высвободившейся энергии по всем $$$n-1$$$ ветвям.

Киа хотела узнать, какую предельную жизненную силу им удастся пробудить. Помогите им вычислить общую сумму $$$f(\text{tree})$$$ по всем допустимым Древам жизни, рождённым их общей связью, по модулю $$$998\,244\,353$$$.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 2\cdot10^5$$$) — размер массива.

Вторая строка содержит $$$n$$$ целых чисел $$$a_1,a_2,\ldots,a_n$$$ ($$$0 \le a_i \lt 2^{18}$$$).

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2\cdot10^5$$$.

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

Для каждого набора входных данных выведите одно целое число — общую сумму $$$f(\text{tree})$$$ по всем допустимым Древам жизни по модулю $$$998\,244\,353$$$.

Пример
Входные данные
5
2
1 2
3
1 1 1
3
1 2 3
4
2 1 4 7
5
5 12 9 14 1
Выходные данные
6
10
40
318
2520
Примечание

В первом наборе входных данных $$$n=2$$$ и $$$a = [1,2]$$$. Можно построить два допустимых дерева: одно с $$$a_1$$$ в корне и $$$a_2$$$ в качестве правого ребёнка и другое с $$$a_2$$$ в корне и $$$a_1$$$ в качестве левого ребёнка.

Если в любом из деревьев разорвать единственную ветвь, останутся две компоненты с XOR-суммами $$$X=1$$$ и $$$Y=2$$$. Таким образом, значение для каждого дерева равно $$$1 + 2 = 3$$$. Суммарная энергия обоих Древьев жизни равна $$$3+3=6$$$.

Во втором наборе входных данных $$$n=3$$$ и $$$a = [1,1,1]$$$.

Можно построить $$$5$$$ допустимых деревьев:

  • Корень равен $$$1$$$: $$$\{(1,2), (2,3)\}$$$, $$$\{(1, 3), (2, 3)\}$$$;
  • Корень равен $$$2$$$: $$$\{(1,2), (2,3)\}$$$;
  • Корень равен $$$3$$$: $$$\{(1,3), (1,2)\}$$$, $$$\{(2, 3), (1, 2)\}$$$.

Каждое дерево представляет собой простой путь, и после разрыва одной ветви остаются две компоненты с XOR-суммами $$$X=1$$$ и $$$Y=0$$$. Поэтому значение для каждого дерева равно $$$2$$$. Суммарная энергия всех пяти Древьев жизни равна $$$5\cdot 2=10$$$.