CF1896H2.Cyclic Hamming (Hard Version)

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 \lt p$ and $a_i \ne b_i$.
• $b$ is a cyclic shift of $a$ if there exists some $0 \leq k \lt p$ such that $b_{(i+k) \bmod p} = a_i$ for all $0 \le i \lt 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$.

这是该问题的困难版本。两个版本之间的唯一区别在于对 $k$ 的约束条件。仅当该问题的所有版本均被解决时，你才可以进行 hack。

在本题陈述中，所有字符串均采用 $0$-索引方式。

对于两个长度均为 $p$ 的字符串 $a$ 和 $b$，我们定义如下概念：

• $a$ 与 $b$ 的汉明距离（Hamming distance），记作 $h(a, b)$，定义为满足 $0 \le i \lt p$ 且 $a_i \ne b_i$ 的下标 $i$ 的个数。
• 若存在某个 $0 \leq k \lt p$，使得对所有 $0 \le i \lt p$ 均有 $b_{(i+k) \bmod p} = a_i$，则称 $b$ 是 $a$ 的一个循环移位（cyclic shift）。其中 $x \bmod y$ 表示 $x$ 除以 $y$ 所得的余数。

给定两个长度均为 $2^{k+1}$ 的二进制字符串 $s$ 和 $t$。这两个字符串中均可能包含缺失字符（用字符 ? 表示）。你的任务是计算将两个字符串中所有缺失字符替换为 '0' 或 '1' 的方案数，使得满足以下条件：

• 字符串 $s$ 和 $t$ 中各自恰好包含 $2^k$ 个字符 '0' 和 $2^k$ 个字符 '1'；
• 对 $t$ 的任意一个循环移位字符串 $c$，均有 $h(s, c) \ge 2^k$。

由于结果可能非常大，请输出答案对 $998\,244\,353$ 取模后的值。

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'.

输入的第一行包含一个整数 $k$（$1 \le k \le 12$）。

输入的第二行包含一个长度为 $2^{k+1}$ 的字符串 $s$，由字符 '0'、'1' 和 '?' 组成。

输入的第三行包含一个长度为 $2^{k+1}$ 的字符串 $t$，由字符 '0'、'1' 和 '?' 组成。

保证字符串 $s$ 和 $t$ 中字符 '0' 与 '1' 的总数均不超过 $2^k$。

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

输出一个整数——该问题答案对 $998\,244\,353$ 取模的结果。

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) \lt 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}$.

在第一个例子中，我们可以验证：对 $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) \lt 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}$。