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

Solution (in CPP):

Solution:
#include <bits/stdc++.h>


using namespace std;

typedef long long ll;
typedef pair<string, string> pss;

const int MAXN = 20;




int n;
string s;
bitset<MAXN> bs;
ll ans;
map<pss, ll> mp1, mp2;



int main() {
	cin >> n >> s;
	reverse(s.begin() + n, s.end());
	do {
		string a, b;
		for (int i = 0; i < n; i++)
			if (bs[i])
				a.push_back(s[i]);
			else
				b.push_back(s[i]);
		mp1[{a, b}]++;
	} while ((bs = bs.to_ulong() + 1) != (1 << n));
	bs = 0;
	do {
		string a, b;
		for (int i = 0; i < n; i++)
			if (bs[i])
				a.push_back(s[n + i]);
			else
				b.push_back(s[n + i]);
		mp2[{a, b}]++;
	} while ((bs = bs.to_ulong() + 1) != (1 << n));
	for (auto i : mp1)
		ans += mp2[i.first] * i.second;
	cout << ans;
	return 0;
}