Description

小B给你一个字符串S。

小B要你给这个串的每个位置染上红色或蓝色，并且满足要求:

•设从左到右读每个染成红色的字符所组成的字符串为S1 , 设从右到左读每个染成蓝色的字符所组成的字符串为S2,则有S1 = S2

Input Format

输入共两行： 第一行有一个整数 N 第二行有一个长度为2N的字符串S

Output Format

输出一个数字，表示满足题目要求的染色方法的方案数

Sample

输入样例 1

4
cabaacba

输出样例 1

4

样例解释1 一共有四种染色方案： • cabaacba • cabaacba • cabaacba • cabaacba

输入样例 2

11
mippiisssisssiipsspiim

输出样例 2

504

输入样例 3

4
abcdefgh

输出样例3

0

Hint

1 < N < 18

字符串的长度为2N

S由小写英文字母构成