题目描述

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

将 $S$ 的每个字符涂成红色或蓝色的方法共有 $2^{2N}$ 种。请问，其中有多少种涂色方案满足以下条件：

• 从左到右读取被涂成红色的字符所组成的字符串，与从右到左读取被涂成蓝色的字符所组成的字符串相同。

输入格式

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

$N$ $S$

输出格式

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

样例 1

输入

4
cabaacba

输出

4

样例 2

输入

11
mippiisssisssiipsspiim

输出

504

样例 3

输入

4
abcdefgh

输出

0

样例 4

输入

18
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

输出

9075135300

说明/提示

限制条件

• $1 \leq N \leq 18$
• $S$ 的长度为 $2N$
• $S$ 仅包含小写英文字母

样例解释 1

存在如下 $4$ 种涂色方案：

样例解释 4

答案可能无法用 32 位整数类型表示。

由 ChatGPT 4.1 翻译