У Кэрол есть последовательность \(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}\).
Выходные данные
Для каждого набора входных данных выведите одно число — ответ на задачу по модулю \(998\,244\,353\).
Примечание
В первом наборе входных данных есть всего \(4\) возможные ситуации:
- \(i_a=1\), \(i_b=1\), \(a=2\), \(b=2\), число шагов равно \(2\);
- \(i_a=1\), \(i_b=2\), \(a=2\), \(b=3\), число шагов равно \(3\);
- \(i_a=2\), \(i_b=1\), \(a=3\), \(b=2\), число шагов равно \(2\);
- \(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\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|