给你一棵有 $$$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