CF1671E.Preorder

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).

你被给定一棵包含 $2^n - 1$ 个顶点的有根树。该树中每个顶点的子节点数要么为 $0$，要么为 $2$。所有叶子节点到根节点的距离均相同；对每个非叶子节点，其两个子节点分别称为左子节点和右子节点。形式上，你被给定的是一棵完美二叉树。

该树的顶点按如下规则编号：

• 根节点编号为 $1$；
• 若某顶点编号为 $x$，则其左子节点编号为 $2x$，右子节点编号为 $2x+1$。

树中每个顶点上写有一个字母，为 A 或 B。记顶点 $x$ 上的字符为 $s_x$。

定义顶点 $x$ 的前序字符串如下：

• 若顶点 $x$ 是叶子节点，则其前序字符串仅由单个字符 $s_x$ 构成；
• 否则，其前序字符串为 $s_x + f(l_x) + f(r_x)$，其中 $+$ 表示字符串连接操作，$f(l_x)$ 表示 $x$ 的左子节点的前序字符串，$f(r_x)$ 表示 $x$ 的右子节点的前序字符串。

整棵树的前序字符串即为其根节点的前序字符串。

现在，正式提出本题问题：

在构造该树的前序字符串之前，你可以执行以下操作任意多次：

• 任选一个非叶子顶点 $x$，交换其左右子节点（即原左子节点变为右子节点，原右子节点变为左子节点）。

你需要计算：通过上述操作所能得到的不同前序字符串的总数。

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.

第一行包含一个整数 $n$（$2 \le n \le 18$）。

第二行包含一个长度为 $2^n-1$ 的字符串 $s_1, s_2, \dots, s_{2^n-1}$，其中每个字符均为 A 或 B。字符之间不包含空格或其他分隔符。

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$.

输出一个整数——即在对给定树执行任意次数题目所述操作后，所能得到的不同先序遍历字符串的个数。由于该数可能非常大，请对 $998244353$ 取模后输出。