H2. Цикличный Хэмминг (сложная версия)
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это сложная версия задачи. Единственное различие между двумя версиями заключается в ограничениях на $$$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$$$ содержала ровно $$$2^k$$$ вхождений каждого символа «0» и «1»;
  • $$$h(s, c) \ge 2^k$$$ для всех строк $$$c$$$, являющихся циклическим сдвигом $$$t$$$.

Поскольку результат может быть очень большим, выведите его по модулю $$$998\,244\,353$$$.

Входные данные

Первая строка содержит одно целое число $$$k$$$ ($$$1 \le k \le 12$$$).

Вторая строка содержит строку $$$s$$$ длины $$$2^{k+1}$$$, состоящую из символов «0», «1» и «?».

Третья строка содержит строку $$$t$$$ длины $$$2^{k+1}$$$, состоящую из символов «0», «1» и «?».

Гарантируется, что обе строки $$$s$$$ и $$$t$$$ содержат не более $$$2^k$$$ символов «0» или «1».

Выходные данные

Выведите одно целое число — ответ на задачу по модулю $$$998\,244\,353$$$.

Примеры
Входные данные
1
0011
0101
Выходные данные
1
Входные данные
1
0011
0110
Выходные данные
0
Входные данные
1
0??1
01??
Выходные данные
2
Входные данные
2
000?????
01010101
Выходные данные
3
Входные данные
2
0???????
1???????
Выходные данные
68
Входные данные
5
0101010101010101010101010101010101010101010101010101010101010101
????????????????????????????????????????????????????????????????
Выходные данные
935297567
Примечание

В первом примере можно проверить, что для всех циклических сдвигов $$$c$$$ из $$$t$$$ выполняется условие $$$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$$$.

Во втором примере существует циклический сдвиг $$$c$$$ строки $$$t$$$ такой, что $$$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}$$$.