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.