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

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

Она выкладывает $$$n$$$ стеклянных бусин в ряд на столе, а затем нанизывает их на ленту. Каждая бусина бывает либо белой, либо чёрной. Бинарная$$$^{\text{∗}}$$$ строка $$$s$$$ обозначает их цвета: символ $$$\mathtt{0}$$$ обозначает белую бусину, а символ $$$\mathtt{1}$$$ — чёрную.

Чтобы сделать эту задачу менее обыденной, Нефрен превращает её в небольшую игру. Она может выполнить следующую операцию любое количество раз (в том числе ноль):

  • Выбрать два индекса $$$l$$$ и $$$r$$$ ($$$1 \le l \le r \le n$$$) таким образом, чтобы $$$s_l=s_r$$$ в текущей строке, и развернуть$$$^{\text{†}}$$$ подстроку $$$s_l s_{l+1}\ldots s_r$$$.

Например, если $$$s=\mathtt{00110}$$$, Нефрен может выбрать $$$l=1$$$ и $$$r=5$$$, поскольку $$$s_1=s_5=\mathtt{0}$$$. После операции строка принимает вид $$$\mathtt{01100}$$$.

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

$$$^{\text{∗}}$$$Бинарная строка — это строка, в которой каждый символ равен либо $$$\mathtt 0$$$, либо $$$\mathtt 1$$$.

$$$^{\text{†}}$$$Развернуть подстроку $$$s_l s_{l+1}\ldots s_r$$$ означает заменить её на $$$s_r s_{r-1}\ldots s_l$$$.

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

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

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

Во второй строке содержится бинарная строка $$$s$$$ длиной $$$n$$$, описывающая цвета бусин.

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

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

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

Пример
Входные данные
4
5
00110
6
001010
5
01010
6
111111
Выходные данные
2
3
1
1
Примечание

В первом наборе входных данных могут быть получены ровно следующие две строки:

  • $$$\mathtt{00110}$$$;
  • $$$\mathtt{01100}$$$.

Например, при развороте всей строки $$$\mathtt{00110}$$$ получается $$$\mathtt{01100}$$$.

Во втором наборе входных данных могут быть получены ровно следующие три строки:

  • $$$\mathtt{001010}$$$;
  • $$$\mathtt{010010}$$$;
  • $$$\mathtt{010100}$$$.

Например, строку $$$\mathtt{010010}$$$ можно получить, развернув первые четыре символа строки $$$\mathtt{001010}$$$, а строку $$$\mathtt{010100}$$$ — развернув всю строку $$$\mathtt{001010}$$$.

В третьем наборе входных данных каждая подстрока, начало и конец которой содержат один и тот же символ, является палиндромом. Следовательно, разворот любой допустимой подстроки не изменяет строку, и можно получить только $$$\mathtt{01010}$$$.

В четвёртом наборе входных данных можно получить только $$$\mathtt{111111}$$$.