#include <iostream>

using namespace std;

typedef long long ll;

int n;
string s;

int n1, n2;
char c1[50], c2[50];

ll d[50][50];

ll calc2() {
    for (int u1 = 0; u1 <= n1; u1++) {
    	for (int u2 = 0; u2 <= n2; u2++) {
    		int p = n-1+u1+u2;
    		d[u1][u2] = u1+u2 == 0;
    		if (u1 > 0 && s[p] == c1[n1-u1]) d[u1][u2] += d[u1-1][u2];
    		if (u2 > 0 && s[p] == c2[n2-u2]) d[u1][u2] += d[u1][u2-1];
    	}
    }
    return d[n1][n2];
}

int main() {
	cin >> n;
	cin >> s;
	ll t = 0;
	for (int b = 0; b < (1<<n); b++) {
		n1 = n2 = 0;
		for (int i = 0; i < n; i++) {
			if (b&(1<<i)) c1[n1++] = s[i];
			else c2[n2++] = s[i];
		}
		t += calc2();
	}
	cout << t << "\n";
}

### Prompt

Please provide a cpp coded solution to the problem described below:

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 <iostream>

using namespace std;

typedef long long ll;

int n;
string s;

int n1, n2;
char c1[50], c2[50];

ll d[50][50];

ll calc2() {
    for (int u1 = 0; u1 <= n1; u1++) {
    	for (int u2 = 0; u2 <= n2; u2++) {
    		int p = n-1+u1+u2;
    		d[u1][u2] = u1+u2 == 0;
    		if (u1 > 0 && s[p] == c1[n1-u1]) d[u1][u2] += d[u1-1][u2];
    		if (u2 > 0 && s[p] == c2[n2-u2]) d[u1][u2] += d[u1][u2-1];
    	}
    }
    return d[n1][n2];
}

int main() {
	cin >> n;
	cin >> s;
	ll t = 0;
	for (int b = 0; b < (1<<n); b++) {
		n1 = n2 = 0;
		for (int i = 0; i < n; i++) {
			if (b&(1<<i)) c1[n1++] = s[i];
			else c2[n2++] = s[i];
		}
		t += calc2();
	}
	cout << t << "\n";
}

```