D. Гибкая строка возвращается
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам даны две бинарные строки $$$a$$$ и $$$b$$$ длины $$$n$$$. На каждом шаге строка $$$a$$$ изменяется следующим образом.

  • Индекс $$$i$$$ ($$$1 \leq i \leq n$$$) выбирается случайным образом. Символ $$$a_i$$$ будет изменится на противоположный. То есть если символ $$$a_i$$$ равен $$$0$$$, то он становится $$$1$$$, а если $$$a_i$$$ равен $$$1$$$, то он становится $$$0$$$.

Чему равняется математическое ожидание количества шагов, необходимого для того, чтобы обе строки стали равными в первый раз?

Бинарная строка — это строка, в которой каждый символ равен либо $$$\tt{0}$$$, либо $$$\tt{1}$$$.

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

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

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

Вторая строка каждого набора содержит бинарную строку $$$a$$$ длиной $$$n$$$.

Третья строка каждого набора содержит бинарную строку $$$b$$$ длины $$$n$$$.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$10^6$$$.

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

Для каждого набора входных данных выведите математическое ожидание количества ходов по модулю $$$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}$$$.

Пример
Входные данные
4
1
0
1
2
00
00
4
1000
1110
5
01001
10111
Выходные данные
1
0
665496254
665496277
Примечание

В первом наборе индекс $$$1$$$ выбирается случайным образом и $$$a_1$$$ изменяется на противоположное значение. После этого строки $$$a$$$ и $$$b$$$ равны. Ожидаемое количество ходов — $$$1$$$.

Во втором наборе строки $$$a$$$ и $$$b$$$ уже равны. Таким образом, ожидаемое количество ходов равно $$$0$$$.

Ожидаемое количество ходов для третьего и четвертого наборов составляет $$$\frac{56}{3}$$$ и $$$\frac{125}{3}$$$ соответственно.