#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define INFL  0x3f3f3f3f3f3f3f3f
#define EPS (1e-10)
using namespace std;
typedef long long ll;
typedef pair<int,int>P;

signed main(){
	//~ int T;cin>>T;
	//~ rep(Case,T){
		//~ ll a,b,c,d;cin>>a>>b>>c>>d;
		
	//~ }
	int n;string s;cin>>n>>s;
	map<pair<string,string>,int>mp;
	rep(i,1<<n){
		string a,b;
		rep(j,n){
			if(i>>j&1)a+=s[j+n];
			else b+=s[j+n];
		}
		mp[{a,b}]++;
		mp[{b,a}]++;
	}
	ll ans=0;
	rep(i,1<<n){
		string a,b;
		rep(j,n){
			if(i>>j&1)a+=s[j];
			else b+=s[j];
		}
		reverse(a.begin(),a.end());
		reverse(b.begin(),b.end());
		ans+=mp[{b,a}];
	}
	cout<<ans/2<<endl;
}
### Prompt

Your challenge is to write 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 <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define INFL  0x3f3f3f3f3f3f3f3f
#define EPS (1e-10)
using namespace std;
typedef long long ll;
typedef pair<int,int>P;

signed main(){
	//~ int T;cin>>T;
	//~ rep(Case,T){
		//~ ll a,b,c,d;cin>>a>>b>>c>>d;
		
	//~ }
	int n;string s;cin>>n>>s;
	map<pair<string,string>,int>mp;
	rep(i,1<<n){
		string a,b;
		rep(j,n){
			if(i>>j&1)a+=s[j+n];
			else b+=s[j+n];
		}
		mp[{a,b}]++;
		mp[{b,a}]++;
	}
	ll ans=0;
	rep(i,1<<n){
		string a,b;
		rep(j,n){
			if(i>>j&1)a+=s[j];
			else b+=s[j];
		}
		reverse(a.begin(),a.end());
		reverse(b.begin(),b.end());
		ans+=mp[{b,a}];
	}
	cout<<ans/2<<endl;
}
```