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

У Кэрол есть последовательность $$$s$$$ из $$$n$$$ неотрицательных целых чисел. Она хочет сыграть с Алисой и Бобом в «Угадайку».

Игра устроена следующим образом. Сначала Кэрол случайно выберет два целых индекса $$$i_a$$$ и $$$i_b$$$ из диапазона $$$[1, n]$$$ и обозначит $$$a=s_{i_a}$$$, $$$b=s_{i_b}$$$. Обратите внимание: $$$i_a$$$ и $$$i_b$$$ могут совпасть.

Затем Кэрол сообщит:

  • значение $$$a$$$ — Алисе;
  • значение $$$b$$$ — Бобу;
  • значение $$$a \mid b$$$ и Алису и Бобу, где $$$|$$$ обозначает операцию побитового ИЛИ.

Обратите внимание: Кэрол не сообщит никакой информации об $$$s$$$ ни Алисе, ни Бобу.

Затем начинается процесс угадывания. Алиса и Боб ходят по очереди, причём первой ходит Алиса. Цель обоих игроков — выяснить, какое из утверждений верно: $$$a < b$$$, $$$a > b$$$, или $$$a = b$$$.

На своём ходу игрок может сделать одно из двух:

  • сказать «Я не знаю» и передать ход другому игроку;
  • сказать «Я знаю», а затем сообщить ответ: «$$$a<b$$$», «$$$a>b$$$», или же «$$$a=b$$$»; после этого игра заканчивается.

Алиса и Боб слышат фразы друг друга и могут использовать их в своих рассуждениях. Оба игрока достаточно умны. Сказать «Я знаю» они могут только в том случае, если точно уверены в ответе.

Найдите математическое ожидание числа шагов в такой игре. Выведите ответ по модулю $$$998\,244\,353$$$.

Формально, пусть $$$M = 998\,244\,353$$$. Можно показать, что ответ может быть представлен в виде несократимой дроби $$$\frac{p}{q}$$$, где $$$p$$$ и $$$q$$$ — целые числа, и $$$q \not \equiv 0 \pmod{M}$$$. Выведите целое число, равное $$$p \cdot q^{-1} \bmod M$$$. Другими словами, выведите такое целое число $$$x$$$, что $$$0 \le x < M$$$ и $$$x \cdot q \equiv p \pmod{M}$$$.

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

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

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

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$s_1,s_2,\ldots, s_n$$$ ($$$0 \le s_i < 2^{30}$$$).

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

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

Для каждого набора входных данных выведите одно число — ответ на задачу по модулю $$$998\,244\,353$$$.

Пример
Входные данные
4
2
2 3
3
0 0 0
3
9 9 6
8
34124838 0 113193378 8 321939321 113193378 9463828 99
Выходные данные
499122179
1
332748120
77987843
Примечание

В первом наборе входных данных есть всего $$$4$$$ возможные ситуации:

  1. $$$i_a=1$$$, $$$i_b=1$$$, $$$a=2$$$, $$$b=2$$$, число шагов равно $$$2$$$;
  2. $$$i_a=1$$$, $$$i_b=2$$$, $$$a=2$$$, $$$b=3$$$, число шагов равно $$$3$$$;
  3. $$$i_a=2$$$, $$$i_b=1$$$, $$$a=3$$$, $$$b=2$$$, число шагов равно $$$2$$$;
  4. $$$i_a=2$$$, $$$i_b=2$$$, $$$a=3$$$, $$$b=3$$$, число шагов равно $$$3$$$.

Математическое ожидание числа шагов равно $$$\frac{2+3+2+3}{4}=\frac{5}{2}=499122179\pmod{998244353}$$$.

Рассмотрим первый случай, когда $$$a=2$$$, $$$b=2$$$. Процесс угадывания происходит следующим образом.

На первом ходу Алиса думает так: «Я знаю, что $$$a=2, a\mid b=2$$$. Можно сделать вывод, что $$$b=0$$$ или $$$b=2$$$, но какой из этих двух случаев имеет место — пока неясно». Поэтому она говорит: «Я не знаю».

На втором ходу Боб думает так: «Я знаю, что $$$b=2, a\mid b=2$$$. Можно сделать вывод, что $$$a=0$$$ или $$$a=2$$$. Однако если $$$a=0$$$, то Алиса на своём ходу уже бы сказала, что $$$a<b$$$. Но она этого не сказала. Значит, $$$a=2$$$». Поэтому он говорит: «Я знаю, $$$a=b$$$». Игра завершается.

Во втором наборе входных данных, при $$$a=0$$$, $$$b=0$$$, Алиса сразу заключает, что $$$a=b$$$. Ожидаемое число ходов равно $$$1$$$.