Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

combinatorics

divide and conquer

dp

dsu

hashing

sortings

trees

*2100

No tag edit access

The problem statement has recently been changed. View the changes.

×
E. Preorder

time limit per test

2 secondsmemory limit per test

512 megabytesinput

standard inputoutput

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

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Aug/08/2024 04:47:05 (i2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|