問題文

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

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

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

制約

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

入力

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

$N$ $S$

出力

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

入力例 1

4
cabaacba

出力例 1

4

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

• c