Problem: You are given a string S of length 2N consisting of lowercase English letters.

There are 2^{2N} ways to color each character in S red or blue. Among these ways, how many satisfy the following condition?

* The string obtained by reading the characters painted red from left to right is equal to the string obtained by reading the characters painted blue from right to left.

Constraints

* 1 \leq N \leq 18
* The length of S is 2N.
* S consists of lowercase English letters.

Input

Input is given from Standard Input in the following format:


N
S


Output

Print the number of ways to paint the string that satisfy the condition.

Examples

Input

4
cabaacba


Output

4


Input

11
mippiisssisssiipsspiim


Output

504


Input

4
abcdefgh


Output

0


Input

18
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa


Output

9075135300

Solution (in CPP):

Solution:
#include<cstdio>
#include<algorithm>
typedef unsigned long long ull;
int N;
char S[50];
ull B,S1[1<<18],S2[1<<18];
int main(){
	scanf("%d%s",&N,S);
	for(int i=B=1;i<=N;i++)B*=233;
	for(int s=0;s<1<<N;s++){
		ull Sr=0,Sb=0;
		for(int j=0;j<N;j++){
			if(s>>j&1)Sb=Sb*233+S[j];
			else Sr=Sr*233+S[j];
		}
		S1[s]=Sr*B+Sb;
		Sr=Sb=0;
		for(int j=N*2;j-->N;){
			if(s>>j-N&1)Sb=Sb*233+S[j];
			else Sr=Sr*233+S[j];
		}
		S2[s]=Sr*B+Sb;
	}
	std::sort(S1,S1+(1<<N));
	std::sort(S2,S2+(1<<N));
	long long ans=0;
	for(int l1=0,r1=0,l2=0,r2=0;l1<1<<N;l1=r1){
		for(;r1<(1<<N)&&S1[l1]==S1[r1];r1++);
		while(l2<(1<<N)&&S2[l2]<S1[l1])l2++;
		while(r2<(1<<N)&&S2[r2]<=S1[l1])r2++;
		ans+=1ll*(r1-l1)*(r2-l2);
	}
	printf("%lld\n",ans);
}