#include<cstdio>
#include<cstring>
#include<algorithm>
#define rep(i,l,r) for (int i=l; i<=r; i++)
typedef long long ll;
using namespace std;

const int N=40;
int n;
ll ans,f[N][N];
bool c[N];
char s[N],a[N],b[N];

void work(){
	int tot=0,tot2=0;
	rep(i,1,n) if (c[i]) a[++tot]=s[i]; else b[++tot2]=s[i];
	reverse(a+1,a+tot+1); reverse(b+1,b+tot2+1);
	memset(f,0,sizeof(f)); f[0][0]=1;
	rep(i,0,n){
		rep(j,0,min(i,tot)) if (f[i][j]) {
			if (j<tot && a[j+1]==s[i+n+1]) f[i+1][j+1]+=f[i][j];
			if (i-j<tot2 && b[i-j+1]==s[i+n+1]) f[i+1][j]+=f[i][j];
		}
	}
	ans+=f[n][tot];
}

void dfs(int x){
	if (x>n){ work(); return; }
	c[x]=1; dfs(x+1); c[x]=0; dfs(x+1);
}

int main(){
	scanf("%d",&n); scanf("%s",s+1);
	dfs(1); printf("%lld\n",ans);
	return 0;
}
### Prompt

In cpp, your task is to solve 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<cstdio>
#include<cstring>
#include<algorithm>
#define rep(i,l,r) for (int i=l; i<=r; i++)
typedef long long ll;
using namespace std;

const int N=40;
int n;
ll ans,f[N][N];
bool c[N];
char s[N],a[N],b[N];

void work(){
	int tot=0,tot2=0;
	rep(i,1,n) if (c[i]) a[++tot]=s[i]; else b[++tot2]=s[i];
	reverse(a+1,a+tot+1); reverse(b+1,b+tot2+1);
	memset(f,0,sizeof(f)); f[0][0]=1;
	rep(i,0,n){
		rep(j,0,min(i,tot)) if (f[i][j]) {
			if (j<tot && a[j+1]==s[i+n+1]) f[i+1][j+1]+=f[i][j];
			if (i-j<tot2 && b[i-j+1]==s[i+n+1]) f[i+1][j]+=f[i][j];
		}
	}
	ans+=f[n][tot];
}

void dfs(int x){
	if (x>n){ work(); return; }
	c[x]=1; dfs(x+1); c[x]=0; dfs(x+1);
}

int main(){
	scanf("%d",&n); scanf("%s",s+1);
	dfs(1); printf("%lld\n",ans);
	return 0;
}
```