A15575. Flexible String Revisit

You are given two binary strings $a$ and $b$ of length $n$ . In each move, the string $a$ is modified in the following way.

- An index $i$ ( $1 \leq i \leq n$ ) is chosen uniformly at random. The character $a_i$ will be flipped. That is, if $a_i$ is $0$ , it becomes $1$ , and if $a_i$ is $1$ , it becomes $0$ .

What is the expected number of moves required to make both strings equal for the first time?

A binary string is a string, in which the character is either $\tt{0}$ or $\tt{1}$ .

The first line contains a single integer $t$ ( $1 \leq t \leq 10^5$ ) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $n$ ( $1 \leq n \leq 10^6$ ) — the length of the strings.

The second line of each test case contains the binary string $a$ of length $n$ .

The third line of each test case contains the binary string $b$ of length $n$ .

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^6$ .

For each test case, output a single line containing the expected number of moves modulo $998\,244\,353$ .

Formally, let $M = 998\,244\,353$ . It can be shown that the answer can be expressed as an irreducible fraction $\frac{p}{q}$ , where $p$ and $q$ are integers and $q \not \equiv 0 \pmod{M}$ . Output the integer equal to $p \cdot q^{-1} \bmod M$ . In other words, output such an integer $x$ that $0 \le x < M$ and $x \cdot q \equiv p \pmod{M}$ .

In the first test case, index $1$ is chosen randomly and $a_1$ is flipped. After the move, the strings $a$ and $b$ are equal. The expected number of moves is $1$ .

The strings $a$ and $b$ are already equal in the second test case. So, the expected number of moves is $0$ .

The expected number of moves for the third and fourth test cases are $\frac{56}{3}$ and $\frac{125}{3}$ respectively.