分数: 600 点
问题陈述
给你一个字符串 S 长度 2N 由小写英文字母组成。
有 2^{2N} 为每个字符着色的方法 S 红色或蓝色。在这些方式中,有多少种满足以下条件?
- 读取涂成红色的字符得到的字符串 从左到右 等于读取蓝色字符得到的字符串 从右到左.
约束
- 1 \leq N \leq 18
- 的长度 S is 2N.
- S 由小写英文字母组成。
输入
输入由标准输入按以下格式给出:
N S
输出
打印满足条件的字符串绘制方式的数量。
示例输入 1
4 cabaacba
示例输出 1
4
绘制字符串有四种方法,如下:
- cabaacba
- cabaacba
- cabaacba
- cabaacba
示例输入 2
11 mippiisssisssiipsspiim
示例输出 2
504
示例输入 3
4 abcdefgh
示例输出 3
0
示例输入 4
18 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
示例输出 4
9075135300
答案可能无法表示为 32位整数。