CF1778D 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.