题目描述

给定一个由小写英文字母组成的长度为 $2N$ 的字符串 $S$。

在这些字符中，有 $2^{2N}$ 种方式可以将字符涂成红色或蓝色。在这些方式中，有多少种满足以下条件的方式：

• 由从左到右涂成红色的字符组成的字符串等于由从右到左涂成蓝色的字符组成的字符串。

约束条件

• $1 \leq N \leq 18$
• 字符串 $S$ 的长度为 $2N$。
• $S$ 由小写英文字母组成。

输入

输入以以下格式从标准输入中给出：

$N$ $S$

输出

输出满足条件的涂色方式的数量。

示例输入 1

4
cabaacba

示例输出 1

4

以下是四种涂色方式：

• c