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>
#define ll long long
using namespace std;
int n;
char s[100],A[2][100];
ll f[100][100];
int main()
{
	scanf("%d",&n);
	scanf("%s",s+1);
	ll ans=0;
	for (int i=0;i<(1<<n);i++)
	{
		int cnt0=0,cnt1=0;
		for (int j=1;j<=n;j++)
			if (!(i&(1<<j-1))) A[0][++cnt0]=s[j];
		for (int j=1;j<=n;j++)
			if (i&(1<<j-1)) A[1][++cnt1]=s[j];
		f[0][0]=1;
		for (int j=1;j<=n;j++)
			for (int k=0;k<=cnt0;k++)
			{
				f[j][k]=0;
				if (k!=0&&s[n+j]==A[0][cnt0-k+1])
					f[j][k]+=f[j-1][k-1];
				if (j!=k&&s[n+j]==A[1][cnt1-(j-k)+1])
					f[j][k]+=f[j-1][k];
			}
		ans+=f[n][cnt0];
	}
	printf("%lld\n",ans);
	return 0;
}