Preorder

题意翻译

### 题目描述 给你一颗 $2^n-1$ 个节点的完美二叉树，按照以下顺序编号： - 根节点编号为 $1$; - 编号为 $x$ 的节点左儿子为 $2x$，右儿子为 $2x+1$。 每个顶点上有一个字母 `A` 或 `B`，在节点 $x$ 上的字母为 $s_x$。 顶点 $x$ 的先序串 $f(x)$ 定义如下： - 如果 $x$ 是叶子，那么 $x$ 的先序串是 $s_x$； - 否则 $x$ 的先序串是 $s_x+f(l_x)+f(r_x)$，其中 $+$ 表示连接两个字符串，$l_x,r_x$ 代表 $x$ 的左右儿子。 一棵树的先序串是根节点的先序串。 允许执行交换任意一个非叶子节点的左右儿子任意次，求树可能的所有不同先序串的个数， 答案模 $998244353$ 。 ### 输入格式 第一行一个整数 $n$（$2\le n\le18$）。 第二行 $2^n-1$ 个字母 `A` 或 `B` 表示 $s_1$ 到 $s_{2^n-1}$，中间没有空格。 ### 输出格式 一个整数表示答案模 $998244353$ 的值。

题目描述

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

输入输出格式

输入格式

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.

输出格式

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

输入输出样例

输入样例 #1

4
BAAAAAAAABBABAB

输出样例 #1

16

输入样例 #2

2
BAA

输出样例 #2

1

输入样例 #3

2
ABA

输出样例 #3

2

输入样例 #4

2
AAB

输出样例 #4

2

输入样例 #5

2
AAA

输出样例 #5

1