这是问题的简单版本。两个版本之间的唯一区别是对 $$$k$$$ 的约束。只有当问题的所有版本都得到解决后,你才能进行黑客攻击。
在此语句中,所有字符串均以 $$$0$$$ 为索引。
对于两个长度相同的字符串 $$$a$$$, $$$b$$$ $$$p$$$,我们定义以下定义:
- $$$a$$$ 和 $$$b$$$ 之间的汉明距离,表示为 $$$h(a, b)$$$,定义为 $$$i$$$ 的位置数,使得 $$$0 \le i < p$$$ 且 $$$a_i \ne b_i$$$。
- $$$b$$$ 是 $$$a$$$ 的循环移位,如果存在一些 $$$0 \leq k < p$$$ 使得 $$$b_{(i+k) \bmod p} = a_i$$$ 对于所有 $$$0 \le i < p$$$。这里 $$$x \bmod y$$$ 表示 $$$x$$$ 除以 $$$y$$$ 的余数。
给你两个二进制字符串 $$$s$$$ 和 $$$t$$$,每个长度为 $$$2^{k+1}$$$。两个字符串都可能包含缺失字符(用字符“?”表示)。您的任务是计算用字符“0”或“1”替换两个字符串中缺失字符的方法数量,以便:
- 每个字符串 $$$s$$$ 和 $$$t$$$ 恰好包含每个字符“0”和“1”的 $$$2^k$$$ 出现次数
- $$$h(s, c) \ge 2^k$$$ 对于所有字符串 $$$c$$$ 来说是 $$$t$$$ 的循环移位。
由于结果可能非常大,因此您应该打印对 $$$998\,244\,353$$$ 取模的值。
输入
输入的第一行包含一个整数 $$$k$$$ ($$$1 \le k \le 7$$$)。
输入的第二行包含大小为 $$$2^{k+1}$$$ 的字符串 $$$s$$$,由字符“0”、“1”和“?”组成。
输入的第三行包含大小为 $$$2^{k+1}$$$ 的字符串 $$$t$$$,由字符“0”、“1”和“?”组成。
保证字符串 $$$s$$$ 和 $$$t$$$ 包含不超过 $$$2^k$$$ 字符“0”或“1”。
输出
打印一个整数 - 问题的答案以 $$$998\,244\,353$$$ 为模。
示例
输入 #1
1 0011 0101
输出 #1
1
输入 #2
1 0011 0110
输出 #2
0
输入 #3
1 0??1 01??
输出 #3
2
输入#4
2 000????? 01010101
输出#4
3
输入 #5
2 0??????? 1???????
输出 #5
68
输入 #6
5 0101010101010101010101010101010101010101010101010101010101010101 ????????????????????????????????????????????????????????????????
输出 #6
935297567
注意
在第一个示例中,我们可以检查 $$$t$$$ 的所有循环移位 $$$c$$$ 的条件 $$$h(s, c) \ge 2^k$$$ 是否得到满足。特别是:
- 对于 $$$c = \mathtt{0101}$$$, $$$h(s, c) = h(\mathtt{0110}, \mathtt{0101}) = 2 \ge 2^1$$$;
- 对于 $$$c = \mathtt{1010}$$$, $$$h(s, c) = h(\mathtt{0110}, \mathtt{1010}) = 2 \ge 2^1$$$。
在第二个示例中,存在 $$$t$$$ 的循环移位 $$$c$$$,使得 $$$h(s, c) < 2^k$$$ (特别是,$$$c = \mathtt{0011}$$$,并且 $$$h(s, c) = h(\mathtt{0011}, \mathtt{0011}) = 0$$$)。
在第三个示例中,有 $$$2$$$ 可能的方法来恢复丢失的字符:
- $$$s = \mathtt{0101}$$$, $$$t = \mathtt{0110}$$$;
- $$$s = \mathtt{0011}$$$,$$$t = \mathtt{0101}$$$。
在第四个示例中,有 $$$3$$$ 可能的方法来恢复丢失的字符:
- $$$s = \mathtt{00011110}$$$, $$$t = \mathtt{01010101}$$$;
- $$$s = \mathtt{00011011}$$$, $$$t = \mathtt{01010101}$$$;
- $$$s = \mathtt{00001111}$$$,$$$t = \mathtt{01010101}$$$。