← 返回题目列表

Codeforces · 1671/E

E. 预购

中文机器翻译题面 查看原题

给你一棵有 $$$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)$$$ 是 $$$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$$$ 取模。

示例

输入 #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