#include <iostream>
#include <string>
#include <map>
#include <vector>
#define int long long
using namespace std;
typedef pair<string, string> P;

int n;
string s;
map<P, int> dp;

int dfs(int dep, string x, string y) {
	if (dep == 2 * n) return 1;
	if (dp.find(P(x, y)) != dp.end()) return dp[P(x, y)];
	
	int ret = 0;
	if (x.length() < n && (y.length() < n - x.length() || y[n - x.length() - 1] == s[dep])) {
		ret += dfs(dep + 1, x + s[dep], y);
	}
	if (y.length() < n && (x.length() < n - y.length() || x[n - y.length() - 1] == s[dep])) {
		ret += dfs(dep + 1, x, y + s[dep]);
	}
	return dp[P(x, y)] = ret;
}

signed main() {
	cin >> n >> s;
	cout << dfs(0, "", "") << endl;
	return 0;
}
### Prompt

Your task is to create 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 <iostream>
#include <string>
#include <map>
#include <vector>
#define int long long
using namespace std;
typedef pair<string, string> P;

int n;
string s;
map<P, int> dp;

int dfs(int dep, string x, string y) {
	if (dep == 2 * n) return 1;
	if (dp.find(P(x, y)) != dp.end()) return dp[P(x, y)];
	
	int ret = 0;
	if (x.length() < n && (y.length() < n - x.length() || y[n - x.length() - 1] == s[dep])) {
		ret += dfs(dep + 1, x + s[dep], y);
	}
	if (y.length() < n && (x.length() < n - y.length() || x[n - y.length() - 1] == s[dep])) {
		ret += dfs(dep + 1, x, y + s[dep]);
	}
	return dp[P(x, y)] = ret;
}

signed main() {
	cin >> n >> s;
	cout << dfs(0, "", "") << endl;
	return 0;
}
```