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;
map <pair<string, string>, int> m;
int b;
string t;
bool td[36];
long long u = 0;
string s(bool s, int k)
{
	string ts = "";
	if(s == 0)
	{
		for(int i = k-b; i < k; i++)
		{
			if(td[i] == 1)
			{
				ts += t[i];
			}
		}
	}
	else
	{
		for(int i = k-1; i >= k-b; i--)
		{
			if(td[i] == 0)
			{
				ts += t[i];
			}
		}
	}
	return ts;
}
void f(int p, int k)
{
	if(p == k)
	{
		if(k == b)
		{
			m[make_pair(s(1, k), s(0, k))]++;
		}
		else
		{
			u += m[make_pair(s(0, k), s(1, k))];
		}
		return;
	}
	f(p+1, k);
	td[p] = 1;
	f(p+1, k);
	td[p] = 0;
}
int main()
{
    cin >> b;
    cin >> t;
    f(0, b);
    f(b, 2*b);
    cout << u <<endl;
}