Вам дана строка \(s\), состоящая из символов «1», «0» и «?». Гарантируется, что первый символ в \(s\) будет «1». Пусть \(m\) будет количеством символов в \(s\).
Подсчитайте количество способов выбрать пару целых чисел \(a, b\), которые удовлетворяют следующему:
- \(1 \leq a < b < 2^m\)
- При записи без начальных нулей двоичные представления \(a\) и \(b\) являются палиндромами.
- Двоичное представление побитового XOR \(a\) и \(b\) подходит под шаблон \(s\). Строка \(t\) подходит под шаблон \(s\), если длины \(t\) и \(s\) одинаковы и для каждого \(i\), \(i\)-й символ \(t\) равен \(i\)-му символу в \(s\), или же \(i\)-й символ в \(s\) равен «?».
Посчитайте это по модулю \(998244353\).
Выходные данные
Выведите одно целое число — количество пар, удовлетворяющих условиям, по модулю \(998244353\).
Примечание
В первом примере, нам подходят \((111, 10001), (11, 10101), (1001, 11111)\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
10110
|
3
|
|
2
|
1?0???10
|
44
|
|
3
|
1?????????????????????????????????????
|
519569202
|
|
4
|
1
|
0
|