Problem Statement

You are given a string $S$ of length $2N$ consisting of lowercase English letters.

There are $2^{2N}$ ways to color each character in $S$ red or blue. Among these ways, how many satisfy the following condition?

• The string obtained by reading the characters painted red from left to right is equal to the string obtained by reading the characters painted blue from right to left.

Constraints

• $1 \\leq N \\leq 18$
• The length of $S$ is $2N$.
• $S$ consists of lowercase English letters.

Input

Input is given from Standard Input in the following format:

$N$ $S$

Output

Print the number of ways to paint the string that satisfy the condition.

Sample Input 1

4
cabaacba

Sample Output 1

4

There are four ways to paint the string, as follows:

• c