Contest Duration: - (local time) (150 minutes) Back to Home
C - String Coloring /

Time Limit: 3 sec / Memory Limit: 1024 MB

### 問題文

S の各文字を赤色か青色かに塗り分ける方法は 2^{2N} 通りありますが，このうち以下の条件を満たす塗り分け方は何通りですか？

• 赤色に塗られた文字を左から右に読んだ文字列と，青色に塗られた文字を右から左に読んだ文字列が一致する

### 制約

• 1 \leq N \leq 18
• S の長さは 2N である
• S は英小文字のみからなる

### 入力

N
S


### 入力例 1

4
cabaacba


### 出力例 1

4


• cabaacba
• cabaacba
• cabaacba
• cabaacba

### 入力例 2

11
mippiisssisssiipsspiim


### 出力例 2

504


### 入力例 3

4
abcdefgh


### 出力例 3

0


### 入力例 4

18
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa


### 出力例 4

9075135300


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.