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

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

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


-----Examples-----

Input
4
BAAAAAAAABBABAB
Output
16
Input
2
BAA
Output
1
Input
2
ABA
Output
2
Input
2
AAB
Output
2
Input
2
AAA
Output
1


-----Note-----

None

Difficulty: HARD
Tags: String algorithms

Combinatorics

Sorting

Tree algorithms

Dynamic programming

Divide and conquer

Spanning trees
Skill types: Dynamic programming

Sorting

Starter code:

Solutions:
import sys
input = lambda : sys.stdin.readline().rstrip('\n\r')
sys.setrecursionlimit(10 ** 6)
from collections import Counter, defaultdict, deque
from itertools import accumulate, chain, zip_longest, product, repeat
from bisect import bisect_left, bisect_right
from math import gcd
from string import ascii_lowercase
from functools import cmp_to_key
mod = 10 ** 9 + 7
mod_2 = 998244353

def node_cost(tree, root):
	if root << 1 >= len(tree):
		return (0, tree[root])
	(cx, sx) = node_cost(tree, root << 1)
	(cy, sy) = node_cost(tree, root << 1 | 1)
	if sx != sy:
		if sx < sy:
			return (cx + cy + 1, tree[root] + sx + sy)
		else:
			return (cx + cy + 1, tree[root] + sy + sx)
	else:
		return (cx + cy, tree[root] + sx + sy)

def solve():
	n = int(input())
	tree = ['$'] + list(input())
	(ans, _) = node_cost(tree, 1)
	return pow(2, ans, mod_2)
val = solve()
print(val)


import sys
N = int(sys.stdin.readline().strip())
s = sys.stdin.readline().strip()
m = 1 << N
mod = 998244353

def dfs(i):
	if i >= m:
		return (1, '')
	(ln, ls) = dfs(i * 2)
	(rn, rs) = dfs(i * 2 + 1)
	if ls < rs:
		return (ln * rn * 2 % mod, ls + s[i - 1] + rs)
	elif ls > rs:
		return (ln * rn * 2 % mod, rs + s[i - 1] + ls)
	else:
		return (ln * rn % mod, ls + s[i - 1] + rs)
(n, _) = dfs(1)
print(n)


if True:

	def compute_hashes(v):
		if v < nodes_count:
			(l, r) = sorted([compute_hashes(2 * v), compute_hashes(2 * v + 1)])
			b[v] = l + b[v] + r
			return b[v]
		return b[v]
	n = int(input())
	nodes_count = 2 ** (n - 1)
	s = input()
	b = ['dum']
	for c in s:
		b.append(c)
	compute_hashes(1)
	res = sum([1 for i in range(1, nodes_count) if b[2 * i] != b[2 * i + 1]])
	print(2 ** res % 998244353)


mod = 998244353
cnt = 0
n = int(input())
s = input()
import random
q = random.randint(10 ** 9, 2 * 10 ** 9)
p = random.randint(10 ** 9, 2 * 10 ** 9)
r = 10 ** 9 + 7
a = [-1]
for i in s:
	if i == 'A':
		a.append(p)
	else:
		a.append(q)
for i in range(2 ** (n - 1) - 1, 0, -1):
	if a[2 * i] != a[2 * i + 1]:
		cnt += 1
	a[i] = a[i] ^ 2 * a[2 * i] + 2 * a[2 * i + 1]
	a[i] %= r
print(pow(2, cnt, mod))


n = int(input())
s = input()
a = [-1]
for i in range(0, 2 ** n - 1):
	if s[i] == 'A':
		a.append('A')
	else:
		a.append('B')
res = 1
for i in range(2 ** (n - 1) - 1, 0, -1):
	if a[2 * i] == a[2 * i + 1]:
		a[i] = a[i] + a[2 * i] + a[2 * i + 1]
	elif a[2 * i] < a[2 * i + 1]:
		res = res * 2 % 998244353
		a[i] = a[i] + a[2 * i] + a[2 * i + 1]
	else:
		res = res * 2 % 998244353
		a[i] = a[i] + a[2 * i + 1] + a[2 * i]
print(res)


MOD = 998244353
(n, s) = (int(input()), input())

def calc(u: int) -> tuple:
	if u >= 1 << n:
		return (0, 0)
	(t1, t2) = (calc(u * 2), calc(u * 2 + 1))
	return (t1[0] + t2[0] + (t1[1] != t2[1]), hash((min(t1[1], t2[1]), max(t1[1], t2[1]), s[u - 1])))
print(pow(2, calc(1)[0], MOD))


N = int(input())
N = 2 ** N
S = input()
U = [0] * N
cnt = 0
for i in range(N - 2, -1, -1):
	a = 2 * i + 1
	b = 2 * i + 2
	if b >= N:
		U[i] = ord(S[i])
		continue
	if U[a] != U[b]:
		cnt += 1
	U[i] = ord(S[i]) + 331 * min(U[a], U[b]) + 3331 * max(U[a], U[b]) + min(U[a], U[b]) ** 2
	U[i] %= 2 ** 104
print(pow(2, cnt, 998244353))


from sys import stdin, setrecursionlimit
input = stdin.readline
setrecursionlimit(10 ** 6)
inp = lambda : list(map(int, input().split()))
mod = 998244353

def add(a, b):
	return (a % mod + b % mod) % mod

def mul(a, b):
	return a % mod * (b % mod) % mod

def solve(i):
	if i >= (1 << n) - 1:
		return ['', 1]
	left = solve(2 * i + 1)
	right = solve(2 * i + 2)
	if left[0] == right[0]:
		ans = mul(left[1], right[1])
	else:
		ans = mul(2 * left[1], right[1])
	st = a[i] + min(left[0], right[0]) + max(left[0], right[0])
	return [st, ans]

def answer():
	ans = solve(0)
	return ans[1]
for T in range(1):
	n = int(input())
	a = input().strip()
	print(answer())


import sys
MOD = 998244353
n = int(next(sys.stdin))
s = next(sys.stdin)
m = len(s) - 1
h = [0 for i in range(m)]
f = [[0, 0] for i in range(m)]
for i in range(m - 1, -1, -1):
	l = (i + 1) * 2 - 1
	r = (i + 1) * 2
	c = int(s[i] == 'B')
	if l < m:
		h[i] = h[l] * 2 + 1
		p1 = min(f[l][0], f[r][0])
		p2 = max(f[l][0], f[r][0])
		f[i][0] = (p1 << h[l]) + p2 + (c << h[i] - 1)
		f[i][1] = f[l][1] * f[r][1] % MOD
		if p1 != p2:
			f[i][1] = f[i][1] * 2 % MOD
	else:
		f[i][0] = c
		f[i][1] = 1
		h[i] = 1
print(f[0][1])


class Node:

	def __init__(self, v, left, right):
		self.v = v
		self.left = left
		self.right = right

	def f(self):
		if self.left is None:
			return (1, self.v)
		(lc, lp) = self.left.f()
		(rc, rp) = self.right.f()
		return ((1 + int(lp != rp)) * lc * rc % 998244353, self.v + ''.join(sorted([lp, rp])))

def construct(s, i):
	if i >= len(s):
		return None
	return Node(s[i], construct(s, i * 2 + 1), construct(s, i * 2 + 2))
n = int(input())
s = input().strip()
print(construct(s, 0).f()[0])


import sys
sys.setrecursionlimit(int(10000000.0))
import functools
n = int(input())
s = input()

class Node:

	def __init__(self, v, left, right):
		self.left = left
		self.right = right
		self.v = v

	@functools.lru_cache(maxsize=None)
	def get_subtree_string(self):
		if not self.left or not self.right:
			return self.v
		if self.left.get_subtree_string() > self.right.get_subtree_string():
			(self.left, self.right) = (self.right, self.left)
		return self.left.get_subtree_string() + self.v + self.right.get_subtree_string()

def cnt_diff(root):
	if not root.left or not root.right:
		return 1
	ret = cnt_diff(root.left) * cnt_diff(root.right)
	ret *= 2 if root.left.get_subtree_string() != root.right.get_subtree_string() else 1
	ret %= 998244353
	return ret
nodes = [None, Node(s[0], None, None)]

def create_tree_from_string(s):
	s = 'x' + s
	for i in range(1, 2 ** n // 2):
		(j, k) = (i * 2, i * 2 + 1)
		nodes.extend([Node(s[j], None, None), Node(s[k], None, None)])
		root = nodes[i]
		(root.left, root.right) = (nodes[j], nodes[k])
	return nodes[1]
root = create_tree_from_string(s)
res = cnt_diff(root)
print(res)