310840: CF1896H2. Cyclic Hamming (Hard Version)

H2. Cyclic Hamming (Hard Version)time limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

This is the hard 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 12$).

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\) 包含恰好 \(2^k\) 个'0'和'1'；
2. 对于 \(t\) 的所有循环移位 \(c\)，都有 \(h(s, c) \ge 2^k\)。

输入输出数据格式：

- 输入：
1. 第一行包含一个整数 \(k\)（\(1 \le k \le 12\)）。
2. 第二行包含一个长度为 \(2^{k+1}\) 的字符串 \(s\)，由字符'0'、'1'和'?'组成。
3. 第三行包含一个长度为 \(2^{k+1}\) 的字符串 \(t\)，由字符'0'、'1'和'?'组成。
- 输出：
输出一个整数，即问题的答案模 \(998,244,353\)。

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