题目描述

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

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

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

输入格式

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

$N$ $S$

输出格式

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

题目大意

给你一个长度为 $2n$ 的由小写字母组成的字符串 $S$。
你可以将每个字符染成红色或蓝色，求有多少种满足以下条件的染色方法。

• 从左到右读红色字符形成的字符串和从右到左读蓝色字符形成的字符串一样。

$1 \le n \le 18$。

4
cabaacba

4

11
mippiisssisssiipsspiim

504

4
abcdefgh

0

18
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

9075135300

提示

制約

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

Sample Explanation 1

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

Sample Explanation 4

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