AT_agc026_c [AGC026C] String Coloring
Description
[problemUrl]: https://atcoder.jp/contests/agc026/tasks/agc026_c
長さ $ 2N $ の，英小文字のみからなる文字列 $ S $ が与えられます。
$ S $ の各文字を赤色か青色かに塗り分ける方法は $ 2^{2N} $ 通りありますが，このうち以下の条件を満たす塗り分け方は何通りですか？
- 赤色に塗られた文字を**左から右に**読んだ文字列と，青色に塗られた文字を**右から左に**読んだ文字列が一致する
Input Format
入力は以下の形式で標準入力から与えられる。
> $ N $ $ S $
Output Format
条件を満たす塗り分け方の個数を出力せよ。
Explanation/Hint
### 制約
- $ 1\ \leq\ N\ \leq\ 18 $
- $ S $ の長さは $ 2N $ である
- $ S $ は英小文字のみからなる
### Sample Explanation 1
以下の $ 4 $ 通りの塗り分け方が存在します
### Sample Explanation 4
答えは32bit整数型で表せないこともあります。