Дано корневое дерево из $$$2^n - 1$$$ вершин. У каждой вершины дерева либо $$$0$$$ сыновей, либо $$$2$$$. Все листья дерева расположены на одинаковой глубине, а у каждой внутренней вершины один из сыновей является левым, а другой — правым. Формально, вам задано совершенное бинарное дерево.
Вершины дерева пронумерованы следующим образом:
На каждой вершине дерева записана буква A или буква B. Пусть буква на вершине $$$x$$$ — это $$$s_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
Название |
---|