Это сложная версия задачи. Единственное различие между двумя версиями заключается в ограничениях на \(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\).
Выходные данные
Выведите одно целое число — ответ на задачу по модулю \(998\,244\,353\).
Примечание
В первом примере можно проверить, что для всех циклических сдвигов \(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}\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1
0011
0101
|
1
|
|
2
|
1
0011
0110
|
0
|
|
3
|
1
0??1
01??
|
2
|
|
4
|
2
000?????
01010101
|
3
|
|
5
|
2
0???????
1???????
|
68
|
|
6
|
5
0101010101010101010101010101010101010101010101010101010101010101
????????????????????????????????????????????????????????????????
|
935297567
|