#include <bits/stdc++.h>
#include <cassert>
#define mod 100000007LL
using namespace std;
typedef long long LL;
typedef pair<LL, LL> pii;
int n;
LL ans;
char s[105];
map<pii,LL> p;
inline int rd() {int r;scanf("%d",&r);return r;}

void dfs1(int dep,LL x,LL y) {
	if (dep > n) {
		p[pii(x, y)]++;
		return ;
	}

	dfs1(dep+1, (x*28LL+s[dep]-'a'+1)%mod, y);
	dfs1(dep+1, x, (y*28LL+s[dep]-'a'+1)%mod);
}

void dfs2(int dep,LL x,LL y) {
	if (dep == n) {
		ans += p[ pii(x, y) ];
		return ;
	}
	
	dfs2(dep-1, (x*28+s[dep]-'a'+1)%mod, y);
	dfs2(dep-1, x, (y*28+s[dep]-'a'+1)%mod);
}

int main() {
	n = rd();
	scanf("%s",s+1);
	dfs1(1,0,0);
	dfs2(2*n,0,0);
	cout << ans << endl;
	return 0;
}
### 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>
#include <cassert>
#define mod 100000007LL
using namespace std;
typedef long long LL;
typedef pair<LL, LL> pii;
int n;
LL ans;
char s[105];
map<pii,LL> p;
inline int rd() {int r;scanf("%d",&r);return r;}

void dfs1(int dep,LL x,LL y) {
	if (dep > n) {
		p[pii(x, y)]++;
		return ;
	}

	dfs1(dep+1, (x*28LL+s[dep]-'a'+1)%mod, y);
	dfs1(dep+1, x, (y*28LL+s[dep]-'a'+1)%mod);
}

void dfs2(int dep,LL x,LL y) {
	if (dep == n) {
		ans += p[ pii(x, y) ];
		return ;
	}
	
	dfs2(dep-1, (x*28+s[dep]-'a'+1)%mod, y);
	dfs2(dep-1, x, (y*28+s[dep]-'a'+1)%mod);
}

int main() {
	n = rd();
	scanf("%s",s+1);
	dfs1(1,0,0);
	dfs2(2*n,0,0);
	cout << ans << endl;
	return 0;
}
```