给定两个二进制字符串 $$$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$$$) — 字符串的长度。
每个测试用例的第二行包含长度为$$$n$$$的二进制字符串$$$a$$$。
每个测试用例的第三行包含长度为$$$n$$$的二进制字符串$$$b$$$。
保证所有测试用例的$$$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}$$$。
示例
输入 #1
4 1 0 1 2 00 00 4 1000 1110 5 01001 10111
输出 #1
1 0 665496254 665496277
注意
在第一个测试用例中,随机选择索引 $$$1$$$ 并翻转 $$$a_1$$$。移动后,字符串 $$$a$$$ 和 $$$b$$$ 相等。预计移动次数为 $$$1$$$。
字符串 $$$a$$$ 和 $$$b$$$ 在第二个测试用例中已经相等。因此,预期的移动次数为 $$$0$$$。
第三个和第四个测试用例的预期移动次数分别为 $$$\frac{56}{3}$$$ 和 $$$\frac{125}{3}$$$。