B. Плитки домино
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Найгглато возвращается с рынка со старой коробкой плиток, надписи на которых уже начали стираться. Ктолли и молодые феи тут же разложили плитки по обеденному столу и превратили их в головоломку.

Есть ряд из $$$n$$$ плиток. Каждая плитка должна быть помечена либо знаком $$$\mathtt 0$$$, либо знаком $$$\mathtt 1$$$. Однако некоторые знаки стёрлись.

Текущий ряд представлен строкой $$$s$$$ длиной $$$n$$$. Каждый символ строки $$$s$$$ — это $$$\mathtt{0}$$$, $$$\mathtt{1}$$$ или $$$\mathtt{?}$$$. Ктолли должна заменить каждый символ $$$\mathtt{?}$$$ на $$$\mathtt{0}$$$ или $$$\mathtt{1}$$$.

После замены для каждого $$$1 \le i \lt n$$$ две соседние плитки $$$s_i$$$ и $$$s_{i+1}$$$ образуют домино веса $$$(s_i + s_{i+1})$$$. Заметим, что два последовательных домино имеют ровно одну общую плитку. Завершённый ряд является допустимым, если каждые два подряд идущих домино имеют различный вес.

Определите количество различных$$$^{\text{∗}}$$$ способов замены всех символов $$$\mathtt{?}$$$ таким образом, чтобы завершённая строка была допустимой. Выведите ответ по модулю $$$998\,244\,353$$$.

$$$^{\text{∗}}$$$Два способа замены считаются различными, если результирующие строки различаются.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

В первой строке каждого набора входных данных содержится одно целое число $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — количество плиток.

Во второй строке содержится строка $$$s$$$ длиной $$$n$$$, где $$$s_i= \mathtt{0}$$$, $$$\mathtt{1}$$$ или $$$\mathtt{?}$$$.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

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

Для каждого набора входных данных выведите одно целое число — количество допустимых способов замены всех символов $$$\mathtt{?}$$$, по модулю $$$998\,244\,353$$$.

Пример
Входные данные
4
2
??
5
0?1??
5
0?0??
8
00110011
Выходные данные
4
2
0
1
Примечание

В первом наборе входных данных имеется только одно домино, поэтому любое завершение является допустимым. Допустимые завершённые строки: $$$\mathtt{00}$$$, $$$\mathtt{01}$$$, $$$\mathtt{10}$$$ и $$$\mathtt{11}$$$.

Во втором наборе входных данных допустимые завершённые строки: $$$\mathtt{00110}$$$ и $$$\mathtt{01100}$$$.

В третьем наборе входных данных допустимых завершённых строк нет.

В четвёртом наборе входных данных единственной допустимой завершённой строкой является $$$\mathtt{00110011}$$$.