C - String Coloring Editorial /

Time Limit: 3 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

長さ 2N の，英小文字のみからなる文字列 S が与えられます。

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

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

制約

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

入力

入力は以下の形式で標準入力から与えられる。

N
S

出力

条件を満たす塗り分け方の個数を出力せよ。

入力例 1

4
cabaacba

出力例 1

4

以下の 4 通りの塗り分け方が存在します。

  • cabaacba
  • cabaacba
  • cabaacba
  • cabaacba

入力例 2

11
mippiisssisssiipsspiim

出力例 2

504

入力例 3

4
abcdefgh

出力例 3

0

入力例 4

18
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

出力例 4

9075135300

答えは32bit整数型で表せないこともあります。

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.