Preorder
Contest: Educational Codeforces Round 127 (Rated for Div. 2)
Difficulty rating: 2100
Tags: combinatorics, divide and conquer, dp, dsu, hashing, sortings, trees

You are given a rooted tree of $$$2^n - 1$$$ vertices. Every vertex of this tree has either $$$0$$$ children, or $$$2$$$ children. All leaves of this tree have the same distance from the root, and for every non-leaf vertex, one of its children is the left one, and the other child is the right one. Formally, you are given a perfect binary tree.

The vertices of the tree are numbered in the following order:

- the root has index $$$1$$$;
- if a vertex has index $$$x$$$, then its left child has index $$$2x$$$, and its right child has index $$$2x+1$$$.

Every vertex of the tree has a letter written on it, either A or B. Let's define the character on the vertex $$$x$$$ as $$$s_x$$$.

Let the preorder string of some vertex $$$x$$$ be defined in the following way:

- if the vertex $$$x$$$ is a leaf, then the preorder string of $$$x$$$ be consisting of only one character $$$s_x$$$;
- otherwise, the preorder string of $$$x$$$ is $$$s_x + f(l_x) + f(r_x)$$$, where $$$+$$$ operator defines concatenation of strings, $$$f(l_x)$$$ is the preorder string of the left child of $$$x$$$, and $$$f(r_x)$$$ is the preorder string of the right child of $$$x$$$.

The preorder string of the tree is the preorder string of its root.

Now, for the problem itself...

You have to calculate the number of different strings that can be obtained as the preorder string of the given tree, if you are allowed to perform the following operation any number of times before constructing the preorder string of the tree:

- choose any non-leaf vertex $$$x$$$, and swap its children (so, the left child becomes the right one, and vice versa).

Input format:
The first line contains one integer $$$n$$$ ($$$2 \le n \le 18$$$).

The second line contains a sequence of $$$2^n-1$$$ characters $$$s_1, s_2, \dots, s_{2^n-1}$$$. Each character is either A or B. The characters are not separated by spaces or anything else.

Output format:
Print one integer — the number of different strings that can be obtained as the preorder string of the given tree, if you can apply any number of operations described in the statement. Since it can be very large, print it modulo $$$998244353$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Example input:
4
BAAAAAAAABBABAB

Example output:
16

Example input:
2
BAA

Example output:
1

Editorial:
In terms of preorder strings, the operation "swap two children of some vertex" means "swap two substrings of equal length in some specific location". This operation can be inverted by applying it an additional time, so for every positive integer $$$k$$$, all of the strings of length $$$2^k-1$$$ are split into equivalence classes in such a way that two strings from the same class can be transformed into each other, and two strings from different classes cannot. For each vertex, the set of its possible preorder strings is one of these classes.
Let's calculate the answer for the problem recursively: let $$$dp_v$$$ be the number of preorder strings for the vertex $$$v$$$. For a leaf, the number of its preorder strings is $$$1$$$. For a vertex $$$x$$$ with children $$$y$$$ and $$$z$$$, one of the two holds:
• if the equivalence class for vertex $$$y$$$ is different from the equivalence class for vertex $$$z$$$, then we have to pick a string from the class of vertex $$$y$$$, pick a string from the class of vertex $$$z$$$, and choose the order in which we take them. So, $$$dp_x = dp_y \cdot dp_z + dp_z \cdot dp_y = 2 \cdot dp_y \cdot dp_z$$$;
• if the equivalence class for $$$y$$$ is the same as the equivalence class for $$$z$$$, then swapping $$$y$$$ and $$$z$$$ doesn't do anything, so we pick a string from the equivalence class of $$$y$$$, and then a string from the equivalence class of $$$z$$$. So, $$$dp_x = dp_y \cdot dp_z = dp_y^2$$$.
The only thing we don't know is how to determine if two vertices represent the same equivalence class. The model solution uses hashing for this, but there's a much simpler method: for each vertex $$$v$$$, let $$$t_v$$$ be the lexicographically smallest string that can be a preorder string of $$$v$$$. If a vertex $$$x$$$ has children $$$y$$$ and $$$z$$$, then $$$t_x = \min(t_y + s_x + t_z, t_z + s_x + t_y)$$$, and we can calculate these strings recursively since the total length is $$$O(n 2^n)$$$ — each of $$$2^n-1$$$ characters will be present in $$$O(n)$$$ strings.