E. Прямой обход
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дано корневое дерево из $$$2^n - 1$$$ вершин. У каждой вершины дерева либо $$$0$$$ сыновей, либо $$$2$$$. Все листья дерева расположены на одинаковой глубине, а у каждой внутренней вершины один из сыновей является левым, а другой — правым. Формально, вам задано совершенное бинарное дерево.

Вершины дерева пронумерованы следующим образом:

  • номер корня — $$$1$$$;
  • если номер внутренней вершины — $$$x$$$, то номер ее левого сына — $$$2x$$$, а номер правого сына — $$$2x+1$$$.

На каждой вершине дерева записана буква A или буква B. Пусть буква на вершине $$$x$$$ — это $$$s_x$$$.

Назовем строкой прямого обхода вершины $$$x$$$ строку, которая строится по следующим правилам:

  • если вершина $$$x$$$ — лист, то строка прямого обхода $$$x$$$ состоит из одного символа $$$s_x$$$;
  • в противном случае строка прямого обхода $$$x$$$ равна $$$s_x + f(l_x) + f(r_x)$$$, где $$$+$$$ обозначает конкатенацию строк, $$$f(l_x)$$$ — строка прямого обхода левого сына $$$x$$$, а $$$f(r_x)$$$ — строка прямого обхода правого сына $$$x$$$.

Строка прямого обхода всего дерева — это строка прямого обхода его корня.

А теперь — сама задача.

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

  • выбрать любую вершину $$$x$$$, не являющуюся листом, и поменять местами ее детей (то есть левый сын становится правым, и наоборот).
Входные данные

В первой строке задано целое число $$$n$$$ ($$$2 \le n \le 18$$$).

Во второй строке заданы $$$2^n-1$$$ символов $$$s_1, s_2, \dots, s_{2^n-1}$$$. Каждый символ —A или B. Символы не разделяются ни пробелами, ни чем-то еще.

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

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

Примеры
Входные данные
4
BAAAAAAAABBABAB
Выходные данные
16
Входные данные
2
BAA
Выходные данные
1
Входные данные
2
ABA
Выходные данные
2
Входные данные
2
AAB
Выходные данные
2
Входные данные
2
AAA
Выходные данные
1