#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using vl = vector<ll>;
using pll = pair<ll, ll>;

#define FOR(i,a,b) for(int i = (a); i < (b); i++)
#define xx first
#define yy second

ll n;
string str;

#define LVL 0

map<tuple<ll, ll, ll, ll, ll>, ll> m;
map<ll, ll> ms[36][36][36][36];

ll doit(ll s, ll redStart, ll redEnd, ll blueStart, ll blueEnd, ll lvl) {
	ll counter = 0;
	// TODO: DP 
	while (redStart < 2 * n && (((1ll<<redStart) & s) == 0)) redStart++;
	while (blueEnd < 2 * n && (((1ll<<blueEnd) & s) == 0)) blueEnd++;
	
	while (redEnd >= 0 && (((1ll<<redEnd) & s) == 0)) redEnd--;
	while (blueStart >= 0 && (((1ll<<blueStart) & s) == 0)) blueStart--;
	
	if (redStart > redEnd && blueStart < blueEnd) return 1;
	if (redStart > redEnd || blueStart < blueEnd) return 0;
	if (redEnd - redStart + 1 < lvl) return 0;
	if (blueStart - blueEnd + 1 < lvl) return 0;
	
	pll red{redStart, redEnd};
	pll blue{blueEnd, blueStart};
	if (blue < red) swap(red, blue);
	
	if (ms[red.xx][red.yy][blue.xx][blue.yy].find(s) != ms[red.xx][red.yy][blue.xx][blue.yy].end())
		return ms[red.xx][red.yy][blue.xx][blue.yy][s];
	
	if (redStart == blueEnd && redEnd == blueStart) {
		// new choice
		ll ns = s - (1ll<<redStart); // remove bit (redStart == blueEnd)
		char c = str[redStart];
		// color red
		for (int i = blueStart; i >= blueEnd; i--) {
			if (str[i] == c && ((1ll<<i) & ns)) {
				ll ns2 = ns - (1ll<<i);
				counter += doit(ns2, redStart + 1, redEnd, i - 1, blueEnd + 1, lvl-1);
			}
		}
		counter *= 2;/*
		// color blue
		for (int i = redEnd; i >= redStart; i--) {
			if (str[i] == c && ((1ll<<i) & ns)) {
				ll ns2 = ns - (1ll<<i);
				counter += doit(ns2, redStart + 1, i - 1, blueStart, blueEnd + 1, lvl-1);
			}
		}*/
	} else if (redStart < blueEnd) {
		// first must be red
		ll ns = s - (1ll<<redStart); // remove bit 
		char c = str[redStart];
		// color red
		for (int i = blueStart; i >= blueEnd; i--) {
			if (str[i] == c && ((1ll<<i) & ns)) {
				ll ns2 = ns - (1ll<<i);
				counter += doit(ns2, redStart + 1, redEnd, i - 1, blueEnd, lvl-1);
			}
		}		
	} else if (blueEnd < redStart) {
		// first must be blue
		ll ns = s - (1ll<<blueEnd); // remove bit
		char c = str[blueEnd];
		// color blue
		for (int i = redEnd; i >= redStart; i--) {
			if (str[i] == c && ((1ll<<i) & ns)) {
				ll ns2 = ns - (1ll<<i);
				counter += doit(ns2, redStart, i - 1, blueStart, blueEnd + 1, lvl-1);
			}
		}	
	}  else if (redEnd > blueStart) {
		// last must be red
		ll ns = s - (1ll<<redEnd);
		char c = str[redEnd];
		// color red
		for (int i = blueEnd; i <= blueStart; i++) {
			if (str[i] == c && ((1ll<<i) & ns)) {
				ll ns2 = ns - (1ll<<i);
				counter += doit(ns2, redStart, redEnd - 1, blueStart, i + 1, lvl-1);
			}
		}
	}  else if (blueStart > redEnd) {
		// last must be blue
		ll ns = s - (1ll<<blueStart);
		char c = str[blueStart];
		// color red
		for (int i = redStart; i <= redEnd; i++) {
			if (str[i] == c && ((1ll<<i) & ns)) {
				ll ns2 = ns - (1ll<<i);
				counter += doit(ns2, i + 1, redEnd, blueStart - 1, blueEnd, lvl-1);
			}
		}
	}
	return ms[red.xx][red.yy][blue.xx][blue.yy][s] = counter;
}

int main() {
	cin >> n >> str;
	cout << doit((1ll<<(2*n))-1, 0, 2*n-1, 2*n-1, 0, n) << endl;
}

Measured memory_bytes: 95360