Home

Contest: Task: Related: TaskB TaskD

Score : $600$ points

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:

  • cabaacba
  • cabaacba
  • cabaacba
  • cabaacba

Sample Input 2

11
mippiisssisssiipsspiim

Sample Output 2

504

Sample Input 3

4
abcdefgh

Sample Output 3

0

Sample Input 4

18
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

Sample Output 4

9075135300

The answer may not be representable as a $32$-bit integer.