配点 : $600$ 点

問題文

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

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

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

制約

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

入力

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

$N$

$S$

出力

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

4
cabaacba

4

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

• cabaacba
• cabaacba
• cabaacba
• cabaacba

11
mippiisssisssiipsspiim

504

4
abcdefgh

0

18
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

9075135300

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