310839: CF1896H1. Cyclic Hamming (Easy Version)

H1. Cyclic Hamming (Easy Version)time limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

This is the easy version of the problem. The only difference between the two versions is the constraint on $k$. You can make hacks only if all versions of the problem are solved.

In this statement, all strings are $0$-indexed.

For two strings $a$, $b$ of the same length $p$, we define the following definitions:

• The hamming distance between $a$ and $b$, denoted as $h(a, b)$, is defined as the number of positions $i$ such that $0 \le i < p$ and $a_i \ne b_i$.
• $b$ is a cyclic shift of $a$ if there exists some $0 \leq k < p$ such that $b_{(i+k) \bmod p} = a_i$ for all $0 \le i < p$. Here $x \bmod y$ denotes the remainder from dividing $x$ by $y$.

You are given two binary strings $s$ and $t$ of length $2^{k+1}$ each. Both strings may contain missing characters (denoted by the character '?'). Your task is to count the number of ways to replace the missing characters in both strings with the characters '0' or '1' such that:

• Each string $s$ and $t$ contains exactly $2^k$ occurrences of each character '0' and '1'
• $h(s, c) \ge 2^k$ for all strings $c$ that is a cyclic shift of $t$.

As the result can be very large, you should print the value modulo $998\,244\,353$.

Input

The first line of the input contains a single integer $k$ ($1 \le k \le 7$).

The second line of the input contains string $s$ of size $2^{k+1}$, consisting of the characters '0', '1' and '?'.

The third line of the input contains string $t$ of size $2^{k+1}$, consisting of the characters '0', '1' and '?'.

It is guaranteed that both strings $s$ and $t$ contains no more than $2^k$ character '0' or '1'.

Output

Print a single integer — the answer to the problem modulo $998\,244\,353$.

ExamplesInput

1
0011
0101

Output

1

Input

1
0011
0110

Output

0

Input

1
0??1
01??

Output

2

Input

2
000?????
01010101

Output

3

Input

2
0???????
1???????

Output

68

Input

5
0101010101010101010101010101010101010101010101010101010101010101
????????????????????????????????????????????????????????????????

Output

935297567

Note

In the first example, we can check that the condition $h(s, c) \ge 2^k$ for all cyclic shift $c$ of $t$ is satisfied. In particular:

• for $c = \mathtt{0101}$, $h(s, c) = h(\mathtt{0110}, \mathtt{0101}) = 2 \ge 2^1$;
• for $c = \mathtt{1010}$, $h(s, c) = h(\mathtt{0110}, \mathtt{1010}) = 2 \ge 2^1$.

In the second example, there exists a cycle shift $c$ of $t$ such that $h(s, c) < 2^k$ (in particular, $c = \mathtt{0011}$, and $h(s, c) = h(\mathtt{0011}, \mathtt{0011}) = 0$).

In the third example, there are $2$ possible ways to recover the missing characters:

• $s = \mathtt{0101}$, $t = \mathtt{0110}$;
• $s = \mathtt{0011}$, $t = \mathtt{0101}$.

In the fourth example, there are $3$ possible ways to recover the missing characters:

• $s = \mathtt{00011110}$, $t = \mathtt{01010101}$;
• $s = \mathtt{00011011}$, $t = \mathtt{01010101}$;
• $s = \mathtt{00001111}$, $t = \mathtt{01010101}$.

题目大意：这是一个关于循环汉明距离的问题。给定两个长度为 \(2^{k+1}\) 的二进制字符串 \(s\) 和 \(t\)，字符串中可能包含缺失的字符（用 '?' 表示）。要求计算有多少种方式可以将两个字符串中的缺失字符替换为 '0' 或 '1'，使得：

1. 字符串 \(s\) 和 \(t\) 中每个字符 '0' 和 '1' 的出现次数都是 \(2^k\)；
2. 对于字符串 \(t\) 的所有循环移位 \(c\)，都满足 \(h(s, c) \ge 2^k\)。

输入输出数据格式：

输入：
- 第一行包含一个整数 \(k\)（\(1 \le k \le 7\)）；
- 第二行包含一个长度为 \(2^{k+1}\) 的字符串 \(s\)，由字符 '0'、'1' 和 '?' 组成；
- 第三行包含一个长度为 \(2^{k+1}\) 的字符串 \(t\)，由字符 '0'、'1' 和 '?' 组成；
- 保证字符串 \(s\) 和 \(t\) 中字符 '0' 或 '1' 的出现次数不超过 \(2^k\)。

输出：
- 输出一个整数，即问题的答案模 \(998\,244\,353\)。

请注意，由于结果可能非常大，所以需要输出模 \(998\,244\,353\) 之后的值。题目大意：这是一个关于循环汉明距离的问题。给定两个长度为 \(2^{k+1}\) 的二进制字符串 \(s\) 和 \(t\)，字符串中可能包含缺失的字符（用 '?' 表示）。要求计算有多少种方式可以将两个字符串中的缺失字符替换为 '0' 或 '1'，使得： 1. 字符串 \(s\) 和 \(t\) 中每个字符 '0' 和 '1' 的出现次数都是 \(2^k\)； 2. 对于字符串 \(t\) 的所有循环移位 \(c\)，都满足 \(h(s, c) \ge 2^k\)。 输入输出数据格式： 输入： - 第一行包含一个整数 \(k\)（\(1 \le k \le 7\)）； - 第二行包含一个长度为 \(2^{k+1}\) 的字符串 \(s\)，由字符 '0'、'1' 和 '?' 组成； - 第三行包含一个长度为 \(2^{k+1}\) 的字符串 \(t\)，由字符 '0'、'1' 和 '?' 组成； - 保证字符串 \(s\) 和 \(t\) 中字符 '0' 或 '1' 的出现次数不超过 \(2^k\)。 输出： - 输出一个整数，即问题的答案模 \(998\,244\,353\)。 请注意，由于结果可能非常大，所以需要输出模 \(998\,244\,353\) 之后的值。