#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
char str[45];
ll dp[45][45];
string a,b;
int main(){
	int n;
	scanf("%d",&n);
	scanf("%s",str+1);
	reverse(str+n+1,str+n+n+1);
	int limt=1<<n;
	ll ans=0;
	for(int s=0;s<limt;s++){
		a=b="";
		memset(dp,0,sizeof dp);
		for(int i=0;i<n;i++){
			if((1<<i)&s) a+=str[i+1];
			else b+=str[i+1];
		}
		dp[0][0]=1;
		for(int i=1;i<=n;i++){
			for(int j=0;j<=(int)a.size();j++){
				if(j+1<=(int)a.size() && str[n+i]==a[j])
					dp[i][j+1]+=dp[i-1][j];
				if(i-j<=(int)b.size() && str[n+i]==b[i-j-1])
					dp[i][j]+=dp[i-1][j];
			}
		}
		ans+=dp[n][a.size()];
	}
	printf("%lld\n",ans);
	return 0;
}
### Prompt

Please create a solution in cpp 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<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
char str[45];
ll dp[45][45];
string a,b;
int main(){
	int n;
	scanf("%d",&n);
	scanf("%s",str+1);
	reverse(str+n+1,str+n+n+1);
	int limt=1<<n;
	ll ans=0;
	for(int s=0;s<limt;s++){
		a=b="";
		memset(dp,0,sizeof dp);
		for(int i=0;i<n;i++){
			if((1<<i)&s) a+=str[i+1];
			else b+=str[i+1];
		}
		dp[0][0]=1;
		for(int i=1;i<=n;i++){
			for(int j=0;j<=(int)a.size();j++){
				if(j+1<=(int)a.size() && str[n+i]==a[j])
					dp[i][j+1]+=dp[i-1][j];
				if(i-j<=(int)b.size() && str[n+i]==b[i-j-1])
					dp[i][j]+=dp[i-1][j];
			}
		}
		ans+=dp[n][a.size()];
	}
	printf("%lld\n",ans);
	return 0;
}
```