卡评测将会被封号。
给定两个长度为 的二进制字符串 和 。每一步，你可以对字符串 进行如下操作：
问：期望需要多少次操作，才能使得 和 第一次完全相等？
二进制字符串是指每个字符都是 或 的字符串。
第一行包含一个整数 （），表示测试用例的数量。接下来是每个测试用例的描述。
每个测试用例的第一行包含一个整数 （），表示字符串的长度。
第二行包含一个长度为 的二进制字符串 。
第三行包含一个长度为 的二进制字符串 。
保证所有测试用例中 的总和不超过 。
对于每个测试用例，输出一行，表示期望的操作次数，对 取模。
形式化地，设 。可以证明答案可以表示为最简分数 ，其中 和 是整数且 。输出一个整数 ，满足 且 。
4 1 0 1 2 00 00 4 1000 1110 5 01001 10111
1 0 665496254 665496277
在第一个测试用例中，随机选择下标 并翻转 ，操作后 和 相等。期望操作次数为 。
在第二个测试用例中， 和 已经相等，所以期望操作次数为 。
第三和第四个测试用例的期望操作次数分别为 和 。
