Вам даны две бинарные строки \(a\) и \(b\) длины \(n\). На каждом шаге строка \(a\) изменяется следующим образом.
- Индекс \(i\) (\(1 \leq i \leq n\)) выбирается случайным образом. Символ \(a_i\) будет изменится на противоположный. То есть если символ \(a_i\) равен \(0\), то он становится \(1\), а если \(a_i\) равен \(1\), то он становится \(0\).
Чему равняется математическое ожидание количества шагов, необходимого для того, чтобы обе строки стали равными в первый раз?
Бинарная строка — это строка, в которой каждый символ равен либо \(\tt{0}\), либо \(\tt{1}\).
Выходные данные
Для каждого набора входных данных выведите математическое ожидание количества ходов по модулю \(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}\).
Примечание
В первом наборе индекс \(1\) выбирается случайным образом и \(a_1\) изменяется на противоположное значение. После этого строки \(a\) и \(b\) равны. Ожидаемое количество ходов — \(1\).
Во втором наборе строки \(a\) и \(b\) уже равны. Таким образом, ожидаемое количество ходов равно \(0\).
Ожидаемое количество ходов для третьего и четвертого наборов составляет \(\frac{56}{3}\) и \(\frac{125}{3}\) соответственно.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
1
0
1
2
00
00
4
1000
1110
5
01001
10111
|
1
0
665496254
665496277
|