#include<map>
#include<cstdio>
#include<algorithm>
using namespace std;
#define mp make_pair
map<pair<long long,long long>,long long>Map;
int n,f[105];
long long ans=0;
char st[105],str[105];
void dfs(int t,int v)
{
	if (t>n)
	{
		long long x=0,y=0;
		for (int i=1; i<=n; i++)
			if (f[i]) x=x*27+st[i]-97+1;
		for (int i=n; i>=1; i--)
			if (!f[i]) y=y*27+st[i]-97+1;
		if (v==0) Map[mp(x,y)]++;
		else ans+=Map[mp(y,x)];
		return;
	}
	f[t]=0; dfs(t+1,v);
	f[t]=1; dfs(t+1,v);
}
int main()
{
	scanf("%d%s",&n,str+1);
	for (int i=1; i<=n; i++) st[i]=str[i]; dfs(1,0);
	for (int i=1; i<=n; i++) st[i]=str[i+n]; dfs(1,1);
	printf("%lld\n",ans);
	return 0;
}


### Prompt

Generate a cpp solution to the following 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

### Response

```cpp
#include<map>
#include<cstdio>
#include<algorithm>
using namespace std;
#define mp make_pair
map<pair<long long,long long>,long long>Map;
int n,f[105];
long long ans=0;
char st[105],str[105];
void dfs(int t,int v)
{
	if (t>n)
	{
		long long x=0,y=0;
		for (int i=1; i<=n; i++)
			if (f[i]) x=x*27+st[i]-97+1;
		for (int i=n; i>=1; i--)
			if (!f[i]) y=y*27+st[i]-97+1;
		if (v==0) Map[mp(x,y)]++;
		else ans+=Map[mp(y,x)];
		return;
	}
	f[t]=0; dfs(t+1,v);
	f[t]=1; dfs(t+1,v);
}
int main()
{
	scanf("%d%s",&n,str+1);
	for (int i=1; i<=n; i++) st[i]=str[i]; dfs(1,0);
	for (int i=1; i<=n; i++) st[i]=str[i+n]; dfs(1,1);
	printf("%lld\n",ans);
	return 0;
}


```