#include <bits/stdc++.h>
using namespace std;

int n;
string s;
int niz[40];
map< pair<string, string>, int > m;
long long int sol = 0;

void rek(int x) {
	if (x == n) {
		
		string s1 = "", s2 = "";
		for (int i = n-1; i >= 0; i --) {
			if (niz[i] == 0) s1 += s[i];
			else s2 += s[i];
		}
		
		m[ make_pair(s1, s2) ] ++;
		return;
	}
	
	
	niz[x] = 0;
	rek(x+1);
	niz[x] = 1;
	rek(x+1);
}

void rj(int x) {
	if (x == 2*n) {
		
		string s1 = "", s2 = "";
		for (int i = n; i < 2*n; i ++) {
			if (niz[i] == 0) s1 += s[i];
			else s2 += s[i];
		}
		
		sol += m[ make_pair(s1, s2) ];
		return;
	}
	
	niz[x] = 0;
	rj(x+1);
	niz[x] = 1;
	rj(x+1);
}

int main () {

	cin >> n >> s;
	rek(0);
	rj(n);
	cout << sol;

	return 0;
}
### Prompt

Please formulate 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>
using namespace std;

int n;
string s;
int niz[40];
map< pair<string, string>, int > m;
long long int sol = 0;

void rek(int x) {
	if (x == n) {
		
		string s1 = "", s2 = "";
		for (int i = n-1; i >= 0; i --) {
			if (niz[i] == 0) s1 += s[i];
			else s2 += s[i];
		}
		
		m[ make_pair(s1, s2) ] ++;
		return;
	}
	
	
	niz[x] = 0;
	rek(x+1);
	niz[x] = 1;
	rek(x+1);
}

void rj(int x) {
	if (x == 2*n) {
		
		string s1 = "", s2 = "";
		for (int i = n; i < 2*n; i ++) {
			if (niz[i] == 0) s1 += s[i];
			else s2 += s[i];
		}
		
		sol += m[ make_pair(s1, s2) ];
		return;
	}
	
	niz[x] = 0;
	rj(x+1);
	niz[x] = 1;
	rj(x+1);
}

int main () {

	cin >> n >> s;
	rek(0);
	rj(n);
	cout << sol;

	return 0;
}
```