You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题意

给定一个长度为 $2 \times n$ 的字符串，仅包含小写字母，现在需要把这个串每个位置染色成黑白两种颜色，要求从左到右阅读黑色的字符等于从右到左阅读白色字符，求不同的染色方案数。

输入格式

输入按以下格式从标准输入给出。

$n$ $s$

输出格式

输出染色方案数

输入输出样例

输入 #1

4
cabaacba

输出 #1

4

输入 #2

11
mippiisssisssiipsspiim

输出 #2

504

限制条件

对于所有的测试点

• $1 \leq n \leq 18$
• 字符串仅包含小写字母

【数据范围】