E. Счетчик ABBA
ограничение по времени на тест
3.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дана строка $$$T$$$ длины $$$n$$$ ($$$n$$$ четное), которая состоит из символов 'a', 'b' и '?'.

Посчитайте количество строк $$$S$$$, которые удовлетворяют следующим условиям:

  • $$$|S|=n$$$;
  • $$$S_i$$$ является либо 'a', либо 'b' для всех $$$1 \le i \le n$$$;
  • $$$S_i=T_i$$$ для всех $$$1 \le i \le n$$$, таких что $$$T_i$$$ не равен '?';
  • Существуют две (возможно, пустые) строки $$$A$$$ и $$$B$$$, такие что $$$S=A+B+B+A$$$. Здесь $$$+$$$ обозначает конкатенацию строк.

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

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

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

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$2 \le n \le 400\,000$$$, $$$n$$$ четное).

Вторая строка каждого набора входных данных содержит строку $$$T$$$ длины $$$n$$$, состоящую из символов 'a', 'b' и '?'.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$400\,000$$$.

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

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

Пример
Входные данные
6
2
a?
2
??
4
a??a
4
ab??
12
??a?b??a??ba
12
?ab???b??a??
Выходные данные
1
2
2
2
10
22
Примечание

Для пятого набора входных данных существует $$$10$$$ подходящих строк:

  1. «aaaabaaaaaba»
  2. «aaaabbaaabba»
  3. «aaabbaaaabba»
  4. «aaabbbaabbba»
  5. «abaabbbaabba»
  6. «ababbbbabbba»
  7. «baaabaaababa»
  8. «baaababaaaba»
  9. «baaabbaabbba»
  10. «baabbabaabba»