E. Идеальный разрез
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дана строка $$$s$$$, состоящая из символов 0, 1 и/или ?.

Назовем двоичную (состоящую из 0 и/или 1) строку идеальной, если вы можете разделить строку на две непустые части: префикс $$$a$$$ и суффикс $$$b$$$, так что $$$a_i \ge b_i$$$ для каждого $$$i$$$ от $$$1$$$ до $$$\min(|a|, |b|)$$$.

Ваша задача — посчитать количество способов заменить все вопросительные знаки (независимо) на нули и единицы так, чтобы получившаяся строка была идеальной. Два способа считаются различными, если существует хотя бы одна позиция, в которой символы в этих двух способах различаются. Поскольку ответ может быть большим, выведите его по модулю $$$998244353$$$.

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

Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.

Единственная строка каждого набора входных данных содержит строку $$$s$$$ ($$$2 \le |s| \le 2 \cdot 10^5$$$), состоящую из символов 0, 1 и/или ?.

Дополнительное ограничение на входные данные: сумма длины строк $$$s$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^5$$$.

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

Для каждого набора входных данных выведите одно целое число — количество способов заменить все вопросительные знаки (независимо) на нули и единицы так, чтобы получившаяся строка была идеальной, взятое по модулю $$$998244353$$$.

Пример
Входные данные
5
0?1
011
????
110?0
0?1?
Выходные данные
1
0
15
2
3
Примечание

В первом наборе входных данных можно получить строку 001, которую можно разрезать на префикс длины $$$1$$$ и суффикс длины $$$2$$$.

В четвертом наборе входных данных можно получить:

  • строку 11010, которую можно разрезать на префикс длины $$$2$$$ и суффикс длины $$$3$$$;
  • строку 11000, которую можно разрезать на префикс длины $$$4$$$ и суффикс длины $$$1$$$.