AtCoder Grand Contest 026 - String Coloring

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

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
def f():
	n = int(input())
	s = list(input())
	(a, b) = (s[n - 1::-1], s[n:])
	from collections import defaultdict
	ad = defaultdict(int)
	bd = defaultdict(int)
	for i in range(2 ** n):
		(sa, ta, sb, tb) = ('', '', '', '')
		for j in range(n):
			if i % 2:
				sa += a[j]
				sb += b[j]
			else:
				ta += a[j]
				tb += b[j]
			i //= 2
		ad[sa, ta] += 1
		bd[sb, tb] += 1
	ans = 0
	for k in ad:
		if k in bd:
			ans += bd[k] * ad[k]
	print(ans)
f()


import sys
from collections import defaultdict
sr = lambda : sys.stdin.readline().rstrip()
ir = lambda : int(sr())
lr = lambda : list(map(int, sr().split()))
N = ir()
S = sr()
answer = 0
latter = S[N:][::-1]
dic_left = defaultdict(int)
for pattern in range(1 << N):
	red = ''
	blue = ''
	for i in range(N):
		if pattern >> i & 1:
			red += S[i]
		else:
			blue += S[i]
	key = (red, blue)
	dic_left[key] += 1
dic_right = defaultdict(int)
for pattern in range(1 << N):
	red = ''
	blue = ''
	for i in range(N):
		if pattern >> i & 1:
			red += latter[i]
		else:
			blue += latter[i]
	key = (red, blue)
	dic_right[key] += 1
answer = 0
for (k, v) in dic_left.items():
	if k in dic_right:
		answer += v * dic_right[k]
print(answer)


n = int(input())
string = input()
ans = 0
if string[:n] == string[2 * n - 1:n - 1:-1]:
	ans += 2
for b in range(1, 2 ** n - 1):
	s = ''
	t = ''
	for c in range(n):
		if b & 2 ** c:
			s += string[c]
		else:
			t += string[c]
	s = s[::-1]
	t = t[::-1]
	ltr = string[n:]
	l = len(s)
	DP = [[0 for i in range(l + 1)] for j in range(n + 1)]
	DP[0][0] = 1
	for i in range(1, n + 1):
		x = ltr[i - 1]
		for j in range(0, min(i + 1, l + 1)):
			if j >= 1 and s[j - 1] == x:
				DP[i][j] += DP[i - 1][j - 1]
			if i - j <= len(t) and t[i - j - 1] == x:
				DP[i][j] += DP[i - 1][j]
	ans += DP[-1][-1]
print(ans)


import itertools
n = int(input())
s = input()
t = s[:n][::-1]
u = s[n:]
dic = dict()
for i in itertools.product(range(2), repeat=n):
	t_ = [''] * 2
	u_ = [''] * 2
	for j in range(n):
		t_[i[j]] += t[j]
		u_[i[j]] += u[j]
	if (t_[0], t_[1]) not in dic:
		dic[t_[0], t_[1]] = [1, 0]
	else:
		dic[t_[0], t_[1]][0] += 1
	if (u_[0], u_[1]) not in dic:
		dic[u_[0], u_[1]] = [0, 1]
	else:
		dic[u_[0], u_[1]][1] += 1
ans = 0
for i in dic.keys():
	ans += dic[i][0] * dic[i][1]
print(ans)


def main():
	from collections import defaultdict
	n = int(input())
	s = list(input())
	L = s[:n]
	R = s[n:]
	R.reverse()
	br_l = defaultdict(int)
	br_r = defaultdict(int)
	L_map = dict()
	for i in range(2 ** n):
		(al, bl, ar, br) = ('', '', '', '')
		for j in range(n):
			if (i >> j) % 2:
				al += L[j]
				ar += R[j]
			else:
				bl += L[j]
				br += R[j]
		br_l[al, bl] += 1
		br_r[ar, br] += 1
	ans = 0
	for k in br_l.keys():
		ans += br_r[k] * br_l[k]
	print(ans)
main()


import sys
from collections import Counter

def input():
	return sys.stdin.readline().strip()

def list2d(a, b, c):
	return [[c] * b for i in range(a)]

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]

def list4d(a, b, c, d, e):
	return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]

def ceil(x, y=1):
	return int(-(-x // y))

def INT():
	return int(input())

def MAP():
	return map(int, input().split())

def LIST(N=None):
	return list(MAP()) if N is None else [INT() for i in range(N)]

def Yes():
	print('Yes')

def No():
	print('No')

def YES():
	print('YES')

def NO():
	print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7
N = INT()
S = input()
S1 = S[:N]
S2 = S[N:][::-1]
d1 = Counter()
d2 = Counter()
for i in range(1 << N):
	(s1_1, s1_2) = ('', '')
	(s2_1, s2_2) = ('', '')
	for j in range(N):
		if i >> j & 1:
			s1_1 += S1[j]
			s2_1 += S2[j]
		else:
			s1_2 += S1[j]
			s2_2 += S2[j]
	d1[s1_1, s1_2] += 1
	d2[s2_1, s2_2] += 1
ans = 0
for (k, v) in d1.items():
	ans += v * d2[k]
print(ans)


import itertools
from collections import defaultdict

def main():
	n = int(input())
	s = input()
	left = s[:n]
	right = s[n:]
	right = right[::-1]
	ans = 0
	for n_r in range(n + 1):
		d_left = defaultdict(lambda : 0)
		d_right = defaultdict(lambda : 0)
		pts = itertools.combinations(list(range(n)), r=n_r)
		for pt in pts:
			b_l = ''
			r_l = ''
			b_r = ''
			r_r = ''
			for i in range(n):
				if i in pt:
					b_l += left[i]
					b_r += right[i]
				else:
					r_l += left[i]
					r_r += right[i]
			d_left[b_l, r_l] += 1
			d_right[b_r, r_r] += 1
		for key in d_left:
			ans += d_left[key] * d_right[key]
	print(ans)
main()


N = int(input())
S = input()
S1 = S[:N]
S2 = S[N:][::-1]
from itertools import groupby, accumulate, product, permutations, combinations
from collections import defaultdict

def half(S):
	dic = defaultdict(lambda : 0)
	for pro in product([0, 1], repeat=N):
		s1 = s2 = ''
		for (i, p) in enumerate(pro):
			s1 += S[i] * p
			s2 += S[i] * (1 - p)
		dic[s1, s2] += 1
	return dic
dic1 = half(S1)
dic2 = half(S2)
ans = 0
for (k, v) in dic1.items():
	ans += v * dic2[k]
print(ans)


from collections import defaultdict
import sys
input = sys.stdin.readline
n = int(input())
S = input().rstrip()
L = S[:n]
R = S[n:][::-1]
C = defaultdict(int)
ans = 0
for i in range(1 << n):
	l = ''
	r = ''
	for (j, s) in enumerate(L):
		if i >> j & 1:
			l += s
		else:
			r += s
	C[l + '.' + r] += 1
for i in range(1 << n):
	l = ''
	r = ''
	for (j, s) in enumerate(R):
		if i >> j & 1:
			l += s
		else:
			r += s
	ans += C[l + '.' + r]
print(ans)


import sys
input = sys.stdin.readline
from collections import *
N = int(input())
s = input()[:-1]
cnt = defaultdict(int)
for S in range(1 << N):
	(red, blue) = ([], [])
	for i in range(N):
		if S >> i & 1:
			red.append(s[i])
		else:
			blue.append(s[i])
	cnt[''.join(red), ''.join(blue)] += 1
s = s[::-1]
ans = 0
for S in range(1 << N):
	(red, blue) = ([], [])
	for i in range(N):
		if S >> i & 1:
			red.append(s[i])
		else:
			blue.append(s[i])
	ans += cnt[''.join(blue), ''.join(red)]
print(ans)


from collections import defaultdict
n = int(input())
s = list(input())
left = s[:n]
right = list(reversed(s[n:]))
DL = defaultdict(int)
for i in range(2 ** n):
	red = []
	blue = []
	for j in range(n):
		if i >> j & 1:
			red.append(left[j])
		else:
			blue.append(left[j])
	DL[''.join(red), ''.join(blue)] += 1
DR = defaultdict(int)
for i in range(2 ** n):
	red = []
	blue = []
	for j in range(n):
		if i >> j & 1:
			red.append(right[j])
		else:
			blue.append(right[j])
	DR[''.join(blue), ''.join(red)] += 1
ans = 0
for (k, v) in DL.items():
	if k in DR:
		ans += v * DR[k]
print(ans)


N = int(input())
S = input()
memo = {}

def dp(s1, s2, l1, l2, r1, r2, i):
	if s1 + s2 in memo:
		return memo[s1 + s2]
	if i == 2 * N:
		ret = int(s1 == s2)
	else:
		ret = 0
		if i % 2 == 0:
			c = S[i // 2]
			if s1[l1] == ' ' and (s2[l1] == ' ' or s2[l1] == c):
				ret += dp(s1[:l1] + c + s1[l1 + 1:], s2, l1 + 1, l2, r1, r2, i + 1)
			if s2[r2] == ' ' and (s1[r2] == ' ' or s1[r2] == c):
				ret += dp(s1, s2[:r2] + c + s2[r2 + 1:], l1, l2, r1, r2 - 1, i + 1)
		else:
			c = S[-(i // 2 + 1)]
			if s1[r1] == ' ' and (s2[r1] == ' ' or s2[r1] == c):
				ret += dp(s1[:r1] + c + s1[r1 + 1:], s2, l1, l2, r1 - 1, r2, i + 1)
			if s2[l2] == ' ' and (s1[l2] == ' ' or s1[l2] == c):
				ret += dp(s1, s2[:l2] + c + s2[l2 + 1:], l1, l2 + 1, r1, r2, i + 1)
	memo[s1 + s2] = ret
	return ret
a = S[0] + ' ' * (N - 1)
b = ' ' * N
print(dp(a, b, 1, 0, N - 1, N - 1, 1) * 2)


N = int(input())
S = input()
T = S[:N]
U = S[N:]
U = U[::-1]
from collections import defaultdict
dd1 = defaultdict(int)
dd2 = defaultdict(int)
for i in range(2 ** N):
	red1 = ''
	blue1 = ''
	red2 = ''
	blue2 = ''
	for j in range(N):
		if i // 2 ** j % 2 == 0:
			red1 = red1 + T[j]
			red2 = red2 + U[j]
		else:
			blue1 = blue1 + T[j]
			blue2 = blue2 + U[j]
	dd1[red1 + ' ' + blue1] += 1
	dd2[red2 + ' ' + blue2] += 1
ans = 0
for key in dd1:
	ans += dd1[key] * dd2[key]
print(ans)


from collections import defaultdict
N = int(input())
S = input()
A = S[:N]
B = S[N:]
B = B[::-1]

def f(A):
	dd = defaultdict(int)
	for i in range(1 << N):
		a = []
		b = []
		for j in range(N):
			if i & 1 << j:
				a.append(A[j])
			else:
				b.append(A[j])
		s = ''.join(a)
		t = ''.join(b)
		dd[s, t] += 1
	return dd
dd1 = f(A)
dd2 = f(B)
ans = 0
for (t, c) in dd1.items():
	ans += dd2[t] * c
print(ans)


import sys
sys.setrecursionlimit(2147483647)
INF = float('inf')
MOD = 10 ** 9 + 7
input = lambda : sys.stdin.readline().rstrip()
from collections import defaultdict

def resolve():
	n = int(input())
	S = input()
	(S, T) = (S[:n], S[2 * n - 1:n - 1:-1])
	C = defaultdict(int)
	for V in range(1 << n):
		s = ''.join([s if V >> i & 1 else '' for (i, s) in enumerate(S)])
		t = ''.join([s if not V >> i & 1 else '' for (i, s) in enumerate(S)])
		C[s, t] += 1
	ans = 0
	for V in range(1 << n):
		s = ''.join([t if V >> i & 1 else '' for (i, t) in enumerate(T)])
		t = ''.join([t if not V >> i & 1 else '' for (i, t) in enumerate(T)])
		ans += C[s, t]
	print(ans)
resolve()


from itertools import product
from collections import defaultdict
n = int(input())
s = input()
(sa, sb) = (s[:n], s[n:][::-1])
(a, b, ans) = (defaultdict(int), defaultdict(int), 0)
for i in product(range(2), repeat=n):
	(wa, wb, wa2, wb2) = ('', '', '', '')
	for j in range(n):
		if i[j]:
			(wa, wb) = (wa + sa[j], wb + sb[j])
		else:
			(wa2, wb2) = (wa2 + sa[j], wb2 + sb[j])
	a[wa, wa2] += 1
	b[wb, wb2] += 1
while a:
	(p, q) = a.popitem()
	ans += q * b[p]
print(ans)


import sys
input = sys.stdin.readline
from collections import defaultdict
from itertools import compress
N = int(input())
S = input().strip()
S1 = S[:N]
S2 = S[N:][::-1]
Ls = defaultdict(lambda : defaultdict(int))

def int2bin(x, N):
	res = [0] * N
	for i in range(N):
		res[N - 1 - i] = x % 2
		x >>= 1
	return res
for i in range(2 ** N):
	bs = int2bin(i, N)
	n = sum(bs)
	R = ''
	B = ''
	for (s, b) in zip(S1, bs):
		if b == 1:
			R += s
		else:
			B += s
	Ls[n][R, B[::-1]] += 1
ans = 0
for i in range(2 ** N):
	bs = int2bin(i, N)
	n = sum(bs)
	R = ''
	B = ''
	for (s, b) in zip(S2, bs):
		if b == 1:
			B += s
		else:
			R += s
	R = R[::-1]
	ans += Ls[n][B, R]
print(ans)


def main():
	from collections import defaultdict
	N = int(input())
	S = str(input())
	dic = defaultdict(int)
	for i in range(2 ** N):
		a = str()
		b = str()
		for j in range(N):
			if i >> j & 1:
				a += S[j + N]
			else:
				b += S[j + N]
		dic[a, b] += 1
	count = 0
	for i in range(2 ** N):
		a = str()
		b = str()
		for j in range(N):
			if i >> j & 1:
				a += S[j]
			else:
				b += S[j]
		count += dic[b[::-1], a[::-1]]
	print(count)
main()


import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10 ** 9))
write = lambda x: sys.stdout.write(x + '\n')
n = int(input())
s = input()
t = s[-1:-n - 1:-1]

def sub(r, b):
	dp = [[0] * (len(b) + 1) for _ in range(len(r) + 1)]
	dp[0][0] = 1
	for i in range(len(r) + 1):
		for j in range(len(b) + 1):
			if i < len(r) and t[i + j] == r[i]:
				dp[i + 1][j] += dp[i][j]
			if j < len(b) and t[i + j] == b[j]:
				dp[i][j + 1] += dp[i][j]
	return dp[len(r)][len(b)]
ans = 0
for bit in range(1 << n):
	r = []
	b = []
	for i in range(n):
		if bit >> i & 1:
			r.append(s[i])
		else:
			b.append(s[i])
	ans += sub(r, b)
print(ans)


def run(n, s):
	sl = s[0:n]
	sr = s[n:2 * n][::-1]
	keys1 = [c[0] + '-' + c[1] for c in comb(sl)]
	keys2 = [c[0] + '-' + c[1] for c in comb(sr)]
	dict = {}
	for key1 in keys1:
		if key1 in dict:
			dict[key1] += 1
		else:
			dict[key1] = 1
	cnt = 0
	for key2 in keys2:
		if key2 in dict:
			cnt += dict[key2]
	return cnt

def comb(s):
	if len(s) == 1:
		return [(s, ''), ('', s)]
	else:
		ret = []
		for c in comb(s[0:len(s) - 1]):
			ret.append((c[0] + s[-1], c[1]))
			ret.append((c[0], c[1] + s[-1]))
		return ret

def read_line():
	n = int(input())
	s = input()
	return (n, s)

def main():
	(n, s) = read_line()
	print(run(n, s))
main()


import sys
input = sys.stdin.readline
sys.setrecursionlimit(pow(10, 6))
from collections import defaultdict

def main():
	n = int(input())
	s = input().strip()
	tmp = defaultdict(lambda : 0)
	for state in range(1 << n):
		(rs, bs) = ('', '')
		for i in range(n):
			if state >> i & 1:
				rs += s[i]
			else:
				bs += s[i]
		tmp[rs, bs] += 1
	ans = 0
	for state in range(1 << n):
		(rs, bs) = ('', '')
		for i in range(n):
			if state >> i & 1:
				rs += s[-i - 1]
			else:
				bs += s[-i - 1]
		ans += tmp[rs, bs]
	print(ans)
main()


from collections import deque

def count(s, t1, t2):
	n = len(s)
	k1 = len(t1)
	k2 = len(t2)
	dp = [[0] * (k1 + 1) for i in range(n + 1)]
	dp[0][0] = 1
	for i in range(n):
		for j in range(k1 + 1):
			if j + 1 < k1 + 1 and t1[j] == s[i]:
				dp[i + 1][j + 1] += dp[i][j]
			if 0 <= i - j and i - j < k2 and (t2[i - j] == s[i]):
				dp[i + 1][j] += dp[i][j]
	return dp[n][k1]
n = int(input())
s = input()
ss = s[n:]
m = 1 << n
ans = 0
for bit_state in range(m):
	red = []
	blue = []
	for i in range(n):
		if 1 << i & bit_state:
			red.append(s[i])
		else:
			blue.append(s[i])
	red = red[::-1]
	blue = blue[::-1]
	ans += count(ss, red, blue)
print(ans)


n = int(input())
s = list(input())
l = s[:n]
r = s[n:][::-1]
d = {}
e = {}
for i in range(1 << n):
	s = t = u = v = ''
	for j in range(n):
		if i >> j & 1:
			s += l[j]
			t += r[j]
		else:
			u += l[j]
			v += r[j]
	d[s, u] = d.get((s, u), 0) + 1
	e[t, v] = e.get((t, v), 0) + 1
a = 0
for i in d.keys():
	a += d[i] * e.get(i, 0)
print(a)


from collections import Counter
N = int(input())
S = input()
ctr1 = Counter()
ctr2 = Counter()
for b in range(2 ** N):
	blue = red = ''
	for k in range(N):
		if b & 1 << k:
			blue += S[k]
		else:
			red += S[k]
	ctr1[blue, red] += 1
T = S[:-N - 1:-1]
for b in range(2 ** N):
	blue = red = ''
	for k in range(N):
		if b & 1 << k:
			blue += T[k]
		else:
			red += T[k]
	ctr2[blue, red] += 1
ans = 0
for (k, v) in ctr1.items():
	ans += v * ctr2[k]
print(ans)


from collections import Counter
from itertools import product
N = int(input())
S = input()
Left = Counter()
Right = Counter()
S_left = S[:N]
S_right = S[2 * N - 1:N - 1:-1]
for B in product(range(2), repeat=N):
	red_left = ''
	blue_left = ''
	red_right = ''
	blue_right = ''
	for i in range(N):
		if B[i]:
			red_left += S_left[i]
			red_right += S_right[i]
		else:
			blue_left += S_left[i]
			blue_right += S_right[i]
	Left[red_left + '|' + blue_left] += 1
	Right[blue_right + '|' + red_right] += 1
ans = 0
for i in Left.keys():
	ans += Left[i] * Right[i]
print(ans)


from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import defaultdict
from bisect import bisect

def read():
	return int(input())

def reads():
	return [int(x) for x in input().split()]
N = read()
S = input()
former = defaultdict(lambda : 0)
latter = defaultdict(lambda : 0)

def power(n):
	return chain(*(combinations(range(n), r) for r in range(n + 1)))

def solve(N, S):
	for p in power(N):
		bs1 = []
		rs1 = []
		bs2 = []
		rs2 = []
		for i in range(N):
			if i in p:
				rs1.append(S[i])
				rs2.append(S[-1 - i])
			else:
				bs1.append(S[i])
				bs2.append(S[-1 - i])
		former[''.join(rs1), ''.join(bs1)] += 1
		latter[''.join(bs2), ''.join(rs2)] += 1
	ans = 0
	for (k, v) in former.items():
		if k in latter:
			ans += v * latter[k]
	return ans
print(solve(N, S))


from collections import defaultdict as dd
n = int(input())
_s = list(map(ord, list(input())))
(s, t) = (_s[:n], _s[:n - 1:-1])
d = dict()
mod = 10 ** 9 + 9

def get(st):
	for bit in range(1 << n):
		u = v = 0
		for (j, e) in enumerate(st):
			if bit & 1 << j:
				u = (u * 100 + e) % mod
			else:
				v = (v * 100 + e) % mod
		yield (u, v)
ans = 0
d = dd(int)
for x in get(s):
	d[x] += 1
for x in get(t):
	ans += d[x]
print(ans)


from collections import defaultdict
printn = lambda x: print(x, end='')
inn = lambda : int(input())
inl = lambda : list(map(int, input().split()))
inm = lambda : map(int, input().split())
ins = lambda : input().strip()
DBG = True
BIG = 10 ** 18
R = 10 ** 9 + 7

def ddprint(x):
	if DBG:
		print(x)
n = inn()
s = ins()
l = s[:n]
r = s[n:]
r = r[::-1]
h = defaultdict(int)
for i in range(2 ** n):
	x = ''
	y = ''
	for j in range(n):
		if (i >> j) % 2 == 0:
			x += l[j]
		else:
			y += l[j]
	h[x, y] += 1
ans = 0
for i in range(2 ** n):
	x = ''
	y = ''
	for j in range(n):
		if (i >> j) % 2 == 0:
			x += r[j]
		else:
			y += r[j]
	if (x, y) in h:
		ans += h[x, y]
print(ans)


import sys, math, itertools, collections, bisect
input = lambda : sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf')
mod = 10 ** 9 + 7
mans = inf
ans = 0
count = 0
pro = 1
n = int(input())
S = input()
s1 = S[:n]
s2 = S[n:][::-1]
C1 = collections.Counter()
C2 = collections.Counter()
for bit in range(2 ** n):
	tmp10 = ''
	tmp11 = ''
	tmp20 = ''
	tmp21 = ''
	for i in range(n):
		if bit >> i & 1:
			tmp10 += s1[i]
			tmp20 += s2[i]
		else:
			tmp11 += s1[i]
			tmp21 += s2[i]
	C1[tmp10, tmp11] += 1
	C2[tmp21, tmp20] += 1
for (key, item) in C1.items():
	ans += C2[key] * item
print(ans)


from collections import defaultdict
N = int(input())
S = input()
S = S[:N] + S[2 * N - 1:N - 1:-1]
ldic = defaultdict(int)
rdic = defaultdict(int)
for i in range(2 ** N):
	lred = ''
	lblue = ''
	rred = ''
	rblue = ''
	for j in range(N):
		if i % 2 == 1:
			lred += S[j]
			rred += S[N + j]
		else:
			lblue += S[j]
			rblue += S[N + j]
		i >>= 1
	ldic[lred, lblue] += 1
	rdic[rred, rblue] += 1
ans = 0
for k in ldic.keys():
	ans += ldic[k] * rdic[k]
print(ans)


import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul
sys.setrecursionlimit(10000)

def read_int():
	return int(input())

def read_int_n():
	return list(map(int, input().split()))

def read_float():
	return float(input())

def read_float_n():
	return list(map(float, input().split()))

def read_str():
	return input().strip()

def read_str_n():
	return list(map(str, input().strip().split()))

def error_print(*args):
	print(*args, file=sys.stderr)

def mt(f):
	import time

	def wrap(*args, **kwargs):
		s = time.time()
		ret = f(*args, **kwargs)
		e = time.time()
		error_print(e - s, 'sec')
		return ret
	return wrap

def ref_slv(N, S):
	ans = 0
	for i in combinations(range(0, 2 * N), N):
		l = []
		r = []
		for j in range(2 * N):
			if j in i:
				l.append(S[j])
			else:
				r.append(S[j])
		if ''.join(l) == ''.join(reversed(r)):
			ans += 1
	return ans

@mt
def slv(N, S):
	ans = 0
	l = S[:N]
	r = S[N:][::-1]
	ld = defaultdict(lambda : 0)
	rd = defaultdict(lambda : 0)
	for i in range(N + 1):
		for j in combinations(range(N), i):
			lb = []
			lr = []
			rb = []
			rr = []
			for k in range(N):
				if k in j:
					lb.append(l[k])
					rr.append(r[k])
				else:
					lr.append(l[k])
					rb.append(r[k])
			ld[''.join(lr), ''.join(lb)] += 1
			rd[''.join(rr), ''.join(rb)] += 1
	for (k, v) in ld.items():
		if k in rd:
			ans += v * rd[k]
	return ans

def main():
	N = read_int()
	S = read_str()
	print(slv(N, S))
main()


from collections import defaultdict
n = int(input())
s = input()
d = defaultdict(int)
s1 = s[:n]
s2 = s[n:][::-1]
for i in range(2 ** n):
	(left, right) = ([], [])
	for j in range(n):
		if i >> j & 1:
			left.append(s1[j])
		else:
			right.append(s1[j])
	d[''.join(left) + '_' + ''.join(right)] += 1
ans = 0
for i in range(2 ** n):
	(left, right) = ([], [])
	for j in range(n):
		if i >> j & 1:
			left.append(s2[j])
		else:
			right.append(s2[j])
	ans += d[''.join(left) + '_' + ''.join(right)]
print(ans)


import collections
n = int(input())
s = input()
s1 = s[:n]
s2 = s[-1:-(n + 1):-1]
s_1 = collections.defaultdict(int)
s_2 = collections.defaultdict(int)
strlist = []
for i in range(2 ** n):
	bin_i = bin(i + 2 ** n)
	sequence1 = ''
	sequence1_inverse = ''
	sequence2 = ''
	sequence2_inverse = ''
	for j in range(n):
		if bin_i[j + 3] == '1':
			sequence1 += s1[j]
			sequence2 += s2[j]
		else:
			sequence1_inverse += s1[j]
			sequence2_inverse += s2[j]
	s_1[sequence1 + '-' + sequence1_inverse] += 1
	s_2[sequence2 + '-' + sequence2_inverse] += 1
ans = 0
for i in dict(s_1):
	ans += s_1.get(i, 0) * s_2.get(i, 0)
print(ans)


import itertools
from collections import Counter
n = int(input())
s = input()
t = s[:n][::-1]
u = s[n:]
tc = Counter()
uc = Counter()
for i in itertools.product(range(2), repeat=n):
	t0 = ''
	t1 = ''
	u0 = ''
	u1 = ''
	for j in range(n):
		if not i[j]:
			t0 += t[j]
			u0 += u[j]
		else:
			t1 += t[j]
			u1 += u[j]
	tc[t0 + '-' + t1] += 1
	uc[u0 + '-' + u1] += 1
ans = 0
for i in tc.keys():
	ans += tc[i] * uc[i]
print(ans)


import itertools
N = int(input())
S = input()
ans = 0
L = dict()
R = dict()
for seq in itertools.product([0, 1], repeat=N):
	T0 = ''
	T1 = ''
	T2 = ''
	T3 = ''
	for i in range(N):
		if seq[i] == 0:
			T0 += S[i]
			T2 += S[-i - 1]
		else:
			T1 += S[i]
			T3 += S[-i - 1]
	a0 = len(T0)
	a1 = len(T1)
	a2 = len(T2)
	a3 = len(T3)
	if (T0, T1) in L:
		L[T0, T1] += 1
	else:
		L[T0, T1] = 1
	if (T2, T3) in R:
		R[T2, T3] += 1
	else:
		R[T2, T3] = 1
for tup in L:
	if tup in R:
		ans += L[tup] * R[tup]
print(ans)


N = int(input())
S = input()
sleft = S[:N]
sright = S[2 * N:N - 1:-1]
(ldict, rchoise) = ({}, [])
count = 0
for i in range(2 ** N):
	red = bin(i)[2:].zfill(N)
	(leftred, rightred, leftblue, rightblue) = ('', '', '', '')
	for j in range(N):
		if red[j] == '1':
			leftred += sleft[j]
			rightred += sright[j]
		else:
			leftblue += sleft[j]
			rightblue += sright[j]
	if leftred + '-' + leftblue in ldict.keys():
		ldict[leftred + '-' + leftblue] += 1
	else:
		ldict[leftred + '-' + leftblue] = 1
	rchoise.append(rightred + '-' + rightblue)
for i in rchoise:
	count += ldict.get(i, 0)
print(count)


import math
import itertools
import queue
import bisect
from collections import deque, defaultdict
import heapq as hpq
from sys import stdin, setrecursionlimit
ipt = stdin.readline
setrecursionlimit(10 ** 7)

def main():
	n = int(ipt())
	s = input()
	ld = defaultdict(int)
	rd = defaultdict(int)
	for i in range(2 ** n):
		r = ''
		b = ''
		for (j, sj) in enumerate(s[:n]):
			if i >> j & 1:
				r += sj
			else:
				b += sj
		ld[r, b] += 1
	for i in range(2 ** n):
		r = ''
		b = ''
		for (j, sj) in enumerate(s[2 * n - 1:n - 1:-1]):
			if i >> j & 1:
				r += sj
			else:
				b += sj
		rd[r, b] += 1
	ans = 0
	for (lk, lv) in ld.items():
		ans += lv * rd[lk]
	print(ans)
	return None
main()


def t():
	n = int(input())
	s = input()
	from collections import defaultdict
	(l, r) = (s[:n], s[-1:-n - 1:-1])
	d = defaultdict(int)
	for i in range(2 ** n):
		a = {j for j in range(n) if (i >> j) % 2}
		d[''.join((l[p] for p in sorted(list(a)))), ''.join((l[o] for o in range(n) if o not in a))] += 1
	ans = 0
	for i in range(2 ** n):
		a = {j for j in range(n) if (i >> j) % 2}
		ans += d[''.join((r[p] for p in sorted(list(a)))), ''.join((r[o] for o in range(n) if o not in a))]
	print(ans)
t()


n = int(input())
s = input()
sl = s[:n]
sr = s[n:][::-1]
from collections import Counter
l = Counter()
r = Counter()
from itertools import product
for m in product([False, True], repeat=n):
	key = [sl[i] for i in range(n) if not m[i]]
	key += ['-']
	key += [sl[i] for i in range(n) if m[i]]
	l[''.join(key)] += 1
	key = [sr[i] for i in range(n) if not m[i]]
	key += ['-']
	key += [sr[i] for i in range(n) if m[i]]
	r[''.join(key)] += 1
ans = sum((l[lk] * r[lk] for lk in l.keys()))
print(ans)


N = int(input())
s = input()
sa = s[:N]
sb = s[N:]
import itertools
ALLIST = list(itertools.product((0, 1), repeat=N))
from collections import defaultdict
STRA = defaultdict(int)
STRB = defaultdict(int)
for i in ALLIST:
	red_a = ''
	blue_a = ''
	red_b = ''
	blue_b = ''
	for j in range(N):
		if i[j] == 0:
			red_a += sa[j]
			red_b += sb[j]
		else:
			blue_a += sa[j]
			blue_b += sb[j]
	STRA[red_a[::-1], blue_a[::-1]] += 1
	STRB[red_b, blue_b] += 1
ANS = 0
for key in STRA:
	ANS += STRA[key] * STRB[key]
print(ANS)


from collections import defaultdict
n = int(input())
s = input()
a = s[:n]
b = s[n:][::-1]
d = defaultdict(int)
e = defaultdict(int)

def cnt(c, d):
	for bit in range(1 << n):
		x = []
		y = []
		for i in range(n):
			if bit >> i & 1:
				x.append(c[i])
			else:
				y.append(c[i])
		d[str(x), str(y)] += 1
cnt(a, d)
cnt(b, e)
ans = 0
for (k, v) in d.items():
	ans += e[k] * v
print(ans)


import sys
input = sys.stdin.readline
n = int(input())
s = input().strip()
memo = {}

def getans(a, b, c):
	while a and c and (a[0] == c[-1]):
		a = a[1:]
		c = c[:-1]
	if a and c:
		return 0
	if b == '':
		if a == '' and c == '':
			return 1
		else:
			return 0
	key = a + '/' + b + '/' + c
	if key in memo:
		return memo[key]
	ans = 0
	for i in range(1, len(b)):
		if b[0] == b[i]:
			ans += getans(a, b[1:i], b[i + 1:] + c)
	ans += getans(a + b[0], b[1:], c)
	memo[key] = ans
	return ans
print(getans('', s, '') * 2)


N = int(input())
S = input()
S1 = S[:N]
S2 = S[N:][::-1]
H = dict()
for i in range(2 ** N):
	t1 = ''.join([s for (j, s) in enumerate(S2) if 2 ** j & i])
	t2 = ''.join([s for (j, s) in enumerate(S2) if not 2 ** j & i])
	k = H.get((t1, t2), 0)
	H[t1, t2] = k + 1
ans = 0
for i in range(2 ** N):
	t1 = ''.join([s for (j, s) in enumerate(S1) if 2 ** j & i])
	t2 = ''.join([s for (j, s) in enumerate(S1) if not 2 ** j & i])
	ans += H.get((t1, t2), 0)
print(ans)


import sys
import socket
if socket.gethostname() in ['N551J', 'F551C']:
	sys.stdin = open('c1.in')

def read_int_list():
	return list(map(int, input().split()))

def read_int():
	return int(input())

def read_str_list():
	return input().split()

def read_str():
	return input()

def solve():
	n = read_int()
	s = read_str()
	cache = {}

	def rec(red, blue):
		if (red, blue) in cache:
			return cache[red, blue]
		nr = len(red)
		nb = len(blue)
		if nr > n or nb > n:
			res = 0
			cache[red, blue] = res
			return res
		if nr + nb == 2 * n:
			res = 1
			cache[red, blue] = res
			return res
		c = s[nr + nb]
		res = 0
		if nr + nb < n or (nr < n and c == blue[nr - n]):
			res += rec(red + c, blue)
		if nr + nb < n or (nb < n and c == red[n - 1 - nb]):
			res += rec(red, c + blue)
		cache[red, blue] = res
		return res
	res2 = rec('', '')
	return res2

def main():
	res = solve()
	print(res)
main()


from collections import defaultdict
n = int(input())
s = input()
s1 = s[:n]
s2 = s[::-1][:n]
d = defaultdict(int)
ans = 0

def paint(str, ptn):
	p = ['', '']
	for i in range(n):
		p[int(2 ** i & ptn > 0)] += str[i]
	return tuple(p)
for i in range(2 ** n):
	d[paint(s1, i)] += 1
for i in range(2 ** n):
	ans += d[paint(s2, i)]
print(ans)


import math, string, itertools, fractions, heapq, collections, re, array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20
eps = 1.0 / 10 ** 10
mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]

def LI():
	return [int(x) for x in sys.stdin.readline().split()]

def LI_():
	return [int(x) - 1 for x in sys.stdin.readline().split()]

def LF():
	return [float(x) for x in sys.stdin.readline().split()]

def LS():
	return sys.stdin.readline().split()

def I():
	return int(sys.stdin.readline())

def F():
	return float(sys.stdin.readline())

def S():
	return input()

def pf(s):
	return print(s, flush=True)

def main():
	n = I()
	s = S()
	s1 = s[:n]
	s2 = s[n:][::-1]
	d1 = collections.defaultdict(int)
	d2 = collections.defaultdict(int)
	ii = [2 ** _ for _ in range(n)]
	for i in range(2 ** n):
		t = t2 = t3 = t4 = ','
		for j in range(n):
			if ii[j] & i:
				t += s1[j]
				t3 += s2[j]
			else:
				t2 += s1[j]
				t4 += s2[j]
		d1[t + t2] += 1
		d2[t3 + t4] += 1
	r = 0
	for k in d1.keys():
		r += d1[k] * d2[k]
	return r
print(main())


from collections import Counter
from itertools import product
N = int(input())
S = list(input())
S_rev = list(reversed(S[N:]))
leftlist = []
rightlist = []
for bit in product(range(2), repeat=N):
	red_left = ''
	blue_left = ''
	red_right = ''
	blue_right = ''
	for j in range(N):
		if bit[j] == 1:
			red_left += S[j]
			blue_right += S_rev[j]
		else:
			blue_left += S[j]
			red_right += S_rev[j]
	leftlist.append(''.join(red_left + '|' + blue_left))
	rightlist.append(''.join(blue_right + '|' + red_right))
left = Counter(leftlist)
right = Counter(rightlist)
answer = 0
for (key, value) in left.items():
	answer += value * right[key]
print(answer)


from collections import Counter
N = int(input())
S = input()
S1 = S[:N]
S2 = S[N:]
S2 = S2[::-1]
rb1 = Counter()
rb2 = Counter()
for i in range(2 ** N):
	flag = bin(i)[2:].zfill(N)
	r1 = ''
	b1 = ''
	r2 = ''
	b2 = ''
	for j in range(N):
		if flag[j] == '0':
			r1 += S1[j]
			r2 += S2[j]
		else:
			b1 = S1[j] + b1
			b2 = S2[j] + b2
	key1 = r1 + '&' + b1
	key2 = r2 + '&' + b2
	rb1[key1] += 1
	rb2[key2] += 1
ans = 0
for key in rb1.keys():
	ans += rb1[key] * rb2[key]
print(ans)


from collections import defaultdict
n = int(input())
s = input()
s1 = s[:n]
s2 = s[n:][::-1]

def makeDic(s):
	dic = defaultdict(int)
	for i in range(2 ** n):
		mask = 1
		c1 = ''
		c2 = ''
		for j in range(n):
			if i & mask:
				c1 += s[j]
			else:
				c2 += s[j]
			mask <<= 1
		dic[c1, c2] += 1
	return dic
dic1 = makeDic(s1)
dic2 = makeDic(s2)
ans = 0
for key in dic1:
	if key in dic2:
		ans += dic1[key] * dic2[key]
print(ans)


import itertools as it
from collections import Counter as c
n = int(input())
a = c()
b = c()
s = input()
q = s[:n]
r = s[n:][::-1]
for i in it.product([0, 1], repeat=n):
	(d, e, f, g) = ('', '', '', '')
	for j in range(n):
		if i[j] == 1:
			d += q[j]
			f += r[j]
		else:
			e += q[j]
			g += r[j]
	a[d, e] += 1
	b[f, g] += 1
print(sum((a[i] * b[i] for i in a.keys())))


from collections import defaultdict
N = int(input())
S = input()
cnt = defaultdict(dict)
for i in range(2 ** N):
	(r, b) = ([], [])
	for j in range(N):
		if i >> j & 1:
			r.append(S[j])
		else:
			b.append(S[j])
	r = ''.join(r)
	b = ''.join(b)
	if b not in cnt[r]:
		cnt[r][b] = 1
	else:
		cnt[r][b] += 1
S = S[::-1]
ans = 0
for i in range(2 ** N):
	(r, b) = ([], [])
	for j in range(N):
		if i >> j & 1:
			r.append(S[j])
		else:
			b.append(S[j])
	r = ''.join(r)
	b = ''.join(b)
	if r in cnt[b]:
		ans += cnt[b][r]
print(ans)


import sys

def I():
	return int(sys.stdin.readline().rstrip())

def LS2():
	return list(sys.stdin.readline().rstrip())
N = I()
S = LS2()
from collections import defaultdict
d_left = defaultdict(int)
d_right = defaultdict(int)
for i in range(2 ** N):
	left_red = ''
	left_blue = ''
	right_red = ''
	right_blue = ''
	for j in range(N):
		if i >> j & 1:
			left_red += S[j]
		else:
			left_blue += S[j]
	for j in range(2 * N - 1, N - 1, -1):
		if i >> j - N & 1:
			right_red += S[j]
		else:
			right_blue += S[j]
	d_left[left_red, left_blue] += 1
	d_right[right_red, right_blue] += 1
ans = 0
for key in d_left.keys():
	ans += d_left[key] * d_right[key]
print(ans)


from collections import defaultdict
n = int(input())
s = input()
a = s[:n]
b = s[n:][::-1]
d = defaultdict(int)
e = defaultdict(int)
for bit in range(1 << n):
	x = ''
	y = ''
	z = ''
	w = ''
	for i in range(n):
		if bit >> i & 1:
			x += a[i]
			z += b[i]
		else:
			y += a[i]
			w += b[i]
	d[x + 'ω' + y] += 1
	e[z + 'ω' + w] += 1
print(sum([e[k] * v for (k, v) in d.items()]))


from collections import defaultdict, deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random

def LI():
	return [int(x) for x in sys.stdin.readline().split()]

def I():
	return int(sys.stdin.readline())

def LS():
	return [list(x) for x in sys.stdin.readline().split()]

def S():
	res = list(sys.stdin.readline())
	if res[-1] == '\n':
		return res[:-1]
	return res

def IR(n):
	return [I() for i in range(n)]

def LIR(n):
	return [LI() for i in range(n)]

def SR(n):
	return [S() for i in range(n)]

def LSR(n):
	return [LS() for i in range(n)]
sys.setrecursionlimit(1000000)
mod = 1000000007

def A():
	return

def B():
	return

def C():
	n = I()
	s = S()
	for i in range(2 * n):
		s[i] = ord(s[i]) - 96
	for i in range(n >> 1):
		(s[i], s[n - i - 1]) = (s[n - i - 1], s[i])
	k = 27
	m = 1 << n
	p = [1 << j for j in range(n)]
	d = defaultdict(lambda : 0)
	for i in range(m):
		r = 0
		b = 0
		for j in range(n):
			if i & p[j]:
				r *= k
				r += s[j]
			else:
				b *= k
				b += s[j]
		d[r, b] += 1
	ans = 0
	for i in range(m):
		r = 0
		b = 0
		for j in range(n):
			if i & p[j]:
				r *= k
				r += s[j + n]
			else:
				b *= k
				b += s[j + n]
		ans += d[r, b]
	print(ans)
	return

def D():
	return

def E():
	return

def F():
	return
C()


def main():
	from collections import defaultdict
	N = int(input())
	S = input()
	(L, R) = (S[:N], S[N * 2 - 1:N - 1:-1])

	def make_counter(s: str) -> defaultdict(int):
		ret = defaultdict(int)
		for bit in range(1 << N):
			(red, blue) = ('', '')
			for j in range(N):
				if bit >> j & 1:
					red += s[j]
				else:
					blue += s[j]
			ret[red + '_' + blue] += 1
		return ret
	ld = make_counter(L)
	rd = make_counter(R)
	print(sum((ld[key] * rd[key] for key in ld)))
main()


ans = 0
from collections import defaultdict
n = int(input())
s = input()
a = s[:n]
b = s[n:][::-1]

def coloring(x):
	N = 1 << n
	dc = defaultdict(int)
	for i in range(N):
		r = ''
		b = ''
		for j in range(n):
			if i >> j & 1:
				r += x[j]
			else:
				b += x[j]
		dc[r + '-' + b] += 1
	return dc
fd = coloring(a)
ld = coloring(b)
for (i, j) in fd.items():
	ans += ld[i] * j
print(ans)


from collections import defaultdict
N = int(input())
S = input()
first = S[:N]
last = S[::-1][:N]
d = defaultdict(int)
ans = 0

def paint(str, ptn):
	p = ['', '']
	for i in range(N):
		p[int(2 ** i & ptn > 0)] += str[i]
	return tuple(p)
for i in range(2 ** N):
	d[paint(first, i)] += 1
for i in range(2 ** N):
	ans += d[paint(last, i)]
print(ans)


N = int(input())
S = input()
(S1, S2) = (S[:N], S[2 * N - 1:N - 1:-1])
(hash_S1, hash_S2) = ({}, {})
for i in range(1 << N):
	red = []
	blue = []
	for j in range(N):
		if i >> j & 1:
			red.append(S1[j])
		else:
			blue.append(S1[j])
	key = ''.join(red) + '+' + ''.join(blue)
	if key in hash_S1:
		hash_S1[key] += 1
	else:
		hash_S1[key] = 1
ans = 0
for i in range(1 << N):
	red = []
	blue = []
	for j in range(N):
		if i >> j & 1:
			red.append(S2[j])
		else:
			blue.append(S2[j])
	key = ''.join(blue) + '+' + ''.join(red)
	if key in hash_S1:
		ans += hash_S1[key]
print(ans)


from collections import defaultdict
N = int(input())
S = input()
left = S[:N]
right = S[:N - 1:-1]
br_pattern = defaultdict(int)
for bit in range(1 << N):
	blue = ''
	red = ''
	for isb in range(N):
		if bit & 1 << isb:
			blue = blue + left[isb]
		else:
			red = red + left[isb]
	br_pattern[blue, red] += 1
ans = 0
for bit in range(1 << N):
	red = ''
	blue = ''
	for isr in range(N):
		if bit & 1 << isr:
			red = red + right[isr]
		else:
			blue = blue + right[isr]
	ans += br_pattern[red, blue]
print(ans)


from collections import defaultdict
n = int(input())
s = input()
ans = 0
cand = defaultdict(int)
for bit in range(1 << n):
	red = []
	blue = []
	for i in range(n):
		if bit >> i & 1:
			red.append(s[i])
		else:
			blue.append(s[i])
	red = ''.join(red[::-1])
	blue = ''.join(blue[::-1])
	cand[red, blue] += 1
for bit in range(1 << n):
	red = []
	blue = []
	for i in range(n):
		if bit >> i & 1:
			red.append(s[n + i])
		else:
			blue.append(s[n + i])
	red = ''.join(red)
	blue = ''.join(blue)
	ans += cand[red, blue]
print(ans)


from collections import Counter

def main():
	n = int(input())
	S = input()
	A = S[:n]
	B = S[n:][::-1]
	ans = 0
	La = []
	for i in range(2 ** n):
		(a1, a2) = ('', '')
		for j in range(n):
			if i >> j & 1:
				a1 += A[j]
			else:
				a2 += A[j]
		La.append(a1 + '#' + a2)
	Da = Counter(La)
	for i in range(2 ** n):
		(b1, b2) = ('', '')
		for j in range(n):
			if i >> j & 1:
				b1 += B[j]
			else:
				b2 += B[j]
		ans += Da[b1 + '#' + b2]
	print(ans)
main()


from collections import Counter
from itertools import product

def getLeft(in_string, N):
	return in_string[:N]

def getRight(in_string, N):
	return in_string[2 * N - 1:N - 1:-1]

def getDict(left_seq):
	tmp_n = len(left_seq)
	r_dict = Counter()
	for bit in product(range(2), repeat=tmp_n):
		red_left = ''
		blue_left = ''
		for i in range(tmp_n):
			if bit[i]:
				red_left += left_seq[i]
			else:
				blue_left += left_seq[i]
		r_dict[red_left + '-' + blue_left] += 1
	return r_dict

def getMatch(left, right):
	res = 0
	for i in left.keys():
		res += left[i] * right[i]
	return res
N = int(input())
Seq = input()
print(getMatch(getDict(getLeft(Seq, N)), getDict(getRight(Seq, N))))


N = int(input())
S = input()
Sl = S[:N]
Sr = S[N:]
from collections import defaultdict
L = defaultdict(int)
R = defaultdict(int)
for i in range(1 << N):
	t1 = ''
	t2 = ''
	for j in range(N):
		if i & 1 << j:
			t1 += Sl[j]
	for j in range(N - 1, -1, -1):
		if not i & 1 << j:
			t2 += Sl[j]
	L[t1, t2] += 1
	t1 = ''
	t2 = ''
	for j in range(N - 1, -1, -1):
		if i & 1 << j:
			t1 += Sr[j]
	for j in range(N):
		if not i & 1 << j:
			t2 += Sr[j]
	R[t1, t2] += 1
ans = 0
for (k, v) in L.items():
	ans += R[k] * v
print(ans)


N = int(input())
S = input()
Sf = S[:N]
Sb = S[N:2 * N]
Sb = Sb[::-1]
ans = 0
for i in range(2 ** N):
	R = []
	B = []
	for k in range(N):
		if i & 1 << k:
			R.append(Sf[k])
		else:
			B.append(Sf[k])
	dp = [[0] * (N + 1) for i in range(N + 1)]
	dp[0][0] = 1
	f = True
	for k in range(1, N + 1):
		for j in range(k):
			if j < len(R):
				if Sb[k - 1] == R[j]:
					dp[k][j + 1] += dp[k - 1][j]
			if 0 <= k - j - 1 < len(B):
				if Sb[k - 1] == B[k - j - 1]:
					dp[k][j] += dp[k - 1][j]
	ans += sum(dp[N])
print(ans)


import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce

def input():
	return sys.stdin.readline().strip()

def INT():
	return int(input())

def MAP():
	return map(int, input().split())

def LIST():
	return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def main():
	N = INT()
	S = input()
	former = S[:N]
	latter = S[N:][::-1]
	dic_f = defaultdict(int)
	dic_l = defaultdict(int)
	for x in product([0, 1], repeat=N):
		tmp_red = ''
		tmp_blue = ''
		for i in range(N):
			if x[i]:
				tmp_red += former[i]
			else:
				tmp_blue += former[i]
		dic_f['{},{}'.format(tmp_red, tmp_blue)] += 1
	for x in product([0, 1], repeat=N):
		tmp_red = ''
		tmp_blue = ''
		for i in range(N):
			if x[i]:
				tmp_red += latter[i]
			else:
				tmp_blue += latter[i]
		dic_l['{},{}'.format(tmp_red, tmp_blue)] += 1
	ans = 0
	for key in dic_f:
		(red_f, blue_f) = key.split(',')
		ans += dic_f[key] * dic_l[key]
	print(ans)
main()


def examA():
	N = I()
	A = LI()
	ans = 0
	for i in range(N - 1):
		if A[i + 1] == A[i]:
			A[i + 1] = 101
			ans += 1
	print(ans)
	return

def examB():
	T = I()
	ans = ['Yes'] * T
	for i in range(T):
		(A, B, C, D) = LI()
		if A < B:
			ans[i] = 'No'
			continue
		if D < B:
			ans[i] = 'No'
			continue
		if C >= B:
			continue
	return

def examC():
	N = I()
	S = SI()
	d1 = defaultdict(int)
	d2 = defaultdict(int)
	loop = 2 ** N
	for i in range(loop):
		curR = ''
		curB = ''
		curR2 = ''
		curB2 = ''
		for j in range(N):
			if i & 1 << j == 1 << j:
				curR += S[j]
				curR2 += S[j + N]
			else:
				curB += S[j]
				curB2 += S[j + N]
		d1[curR, curB] += 1
		d2[curR2, curB2] += 1
	ans = 0
	for (key, i) in d1.items():
		cur = i * d2[key[1][::-1], key[0][::-1]]
		ans += cur
	print(ans)
	return
import sys, copy, bisect, itertools, heapq, math
from heapq import heappop, heappush, heapify
from collections import Counter, defaultdict, deque

def I():
	return int(sys.stdin.readline())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def LSI():
	return list(map(str, sys.stdin.readline().split()))

def LS():
	return sys.stdin.readline().split()

def SI():
	return sys.stdin.readline().strip()
global mod, inf
mod = 10 ** 9 + 7
inf = 10 ** 18
examC()


from collections import defaultdict
con = 10 ** 9 + 7
INF = float('inf')

def getlist():
	return list(map(int, input().split()))

def main():
	N = int(input())
	S = input()
	D1 = defaultdict(int)
	D2 = defaultdict(int)
	for i in range(1 << N):
		R = ''
		B = ''
		for j in range(N):
			if i >> j & 1 == 1:
				R += S[j]
			else:
				B += S[j]
		RB = R + ',' + B
		D1[RB] += 1
	for i in range(1 << N):
		R = ''
		B = ''
		for j in range(N):
			if i >> j & 1 == 1:
				R += S[-1 - j]
			else:
				B += S[-1 - j]
		RB = R + ',' + B
		D2[RB] += 1
	ans = 0
	for i in D1:
		ans += D1[i] * D2[i]
	print(ans)
main()


from itertools import product, compress
from collections import Counter
N = int(input())
Ss = input()
S1s = Ss[:N]
ptn1s = [''.join(compress(S1s, sels)) for sels in product(range(2), repeat=N)]
cnt1 = Counter([(red, blue) for (red, blue) in zip(ptn1s, reversed(ptn1s))])
S2s = Ss[N:][::-1]
ptn2s = [''.join(compress(S2s, sels)) for sels in product(range(2), repeat=N)]
cnt2 = Counter([(red, blue) for (red, blue) in zip(ptn2s, reversed(ptn2s))])
ans = 0
for (ptn1, num1) in cnt1.items():
	ans += num1 * cnt2[ptn1]
print(ans)


from itertools import combinations
from collections import defaultdict
n = int(input())
s = input()
d = defaultdict(int)
left = set()
for r in range(n + 1):
	for cl in combinations(range(n), r):
		sl = ''
		sr = ''
		for i in range(n):
			if i in cl:
				sl += s[i]
			else:
				sr += s[i]
		left.add(sl + ',' + sr)
		d[sl + ',' + sr] += 1
res = 0
for r in range(n + 1):
	for cl in combinations(range(n, 2 * n), r):
		sl = ''
		sr = ''
		for i in range(n, 2 * n):
			if i in cl:
				sl = s[i] + sl
			else:
				sr = s[i] + sr
		if sr + ',' + sl in left:
			res += d[sr + ',' + sl]
print(res)


def main():
	n = int(input())
	s = input()
	d1 = dict()
	d2 = dict()
	temp1 = [None] * n
	temp2 = [None] * n
	for ii in range(2 ** n):
		i = ('0' * n + bin(ii)[2:])[-n:]
		cnt1 = 0
		cnt2 = n - 1
		for (k, j) in enumerate(i):
			if j == '1':
				temp1[cnt1] = s[k]
				temp2[cnt1] = s[2 * n - k - 1]
				cnt1 += 1
			else:
				temp1[cnt2] = s[k]
				temp2[cnt2] = s[2 * n - k - 1]
				cnt2 -= 1
		t1 = ''.join(temp1)
		t2 = ''.join(temp2)
		if (t1, cnt1) not in d1.keys():
			d1[t1, cnt1] = 1
		else:
			d1[t1, cnt1] += 1
		if (t2, cnt1) not in d2.keys():
			d2[t2, cnt1] = 1
		else:
			d2[t2, cnt1] += 1
	ans = 0
	for (i, j) in d1.items():
		if i in d2.keys():
			ans += j * d2[i]
	print(ans)
main()


def f(i, k):
	if i == n and k == 0:
		global d
		(hr1, hb1) = (0, 0)
		(hr2, hb2) = (0, 0)
		(cntr, cntb) = (0, 0)
		for j in range(n):
			if c[j]:
				hr1 += x[j] * pow(b1, cntr, mod)
				hr2 += x[j] * pow(b2, cntr, mod)
				hr1 %= mod
				hr2 %= mod
				cntr += 1
			else:
				hb1 += x[j] * pow(b1, cntb, mod)
				hb2 += x[j] * pow(b2, cntb, mod)
				hb1 %= mod
				hb2 %= mod
				cntb += 1
		if min(cntr, cntb) == 0:
			return
		if (hr1, hr2, hb1, hb2) in d:
			d[hr1, hr2, hb1, hb2] += 1
		else:
			d[hr1, hr2, hb1, hb2] = 1
		return
	elif i == n and k == 1:
		(hr1, hb1) = (0, 0)
		(hr2, hb2) = (0, 0)
		(cntr, cntb) = (0, 0)
		for j in range(n):
			if c[j]:
				hr1 += y[j] * powb1[cntr]
				hr2 += y[j] * powb2[cntr]
				hr1 %= mod
				hr2 %= mod
				cntr += 1
			else:
				hb1 += y[j] * powb1[cntb]
				hb2 += y[j] * powb2[cntb]
				hb1 %= mod
				hb2 %= mod
				cntb += 1
		if min(cntr, cntb) == 0:
			return
		if (hr1, hr2, hb1, hb2) in d:
			global ans
			ans += d[hr1, hr2, hb1, hb2]
		return
	c[i] = 1
	f(i + 1, k)
	c[i] = 0
	f(i + 1, k)
n = int(input())
s = list(input())
mod = pow(2, 31) - 1
(b1, b2) = (27, 31)
powb1 = [pow(27, i, mod) for i in range(n)]
powb2 = [pow(31, i, mod) for i in range(n)]
d = {}
(x, y) = ([], [])
for i in range(n):
	x.append(ord(s[i]) - 96)
	y.append(ord(s[-(i + 1)]) - 96)
ans = 0 if not x == y else 2
c = [0] * n
f(0, 0)
c = [0] * n
f(0, 1)
print(ans)


N = int(input())
S = input()
(S1, S2) = (S[:N], S[N:][::-1])
dic = {}
Ans = 0
keys = []
for i in range(2 ** N):
	(red, blue) = ('', '')
	(red2, blue2) = ('', '')
	bits = bin(2 ** N + i)[3:]
	for j in range(N):
		if bits[j] == '0':
			red += S1[j]
			red2 += S2[j]
		else:
			blue += S1[j]
			blue2 += S2[j]
	keys.append(red2 + '-' + blue2)
	key = red + '-' + blue
	if key not in dic.keys():
		dic[key] = 1
	else:
		dic[key] += 1
for k in keys:
	Ans += dic.get(k, 0)
print(Ans)


import itertools
import os
import sys
from collections import defaultdict
if os.getenv('LOCAL'):
	sys.stdin = open('_in.txt', 'r')
sys.setrecursionlimit(2147483647)
INF = float('inf')
IINF = 10 ** 18
MOD = 10 ** 9 + 7
N = int(sys.stdin.readline())
S = sys.stdin.readline().rstrip()

def test(N, S):
	import numpy as np
	S = np.array(list(S))
	ret = 0
	for r in itertools.combinations(range(N * 2), r=N):
		r = np.array(np.bincount(r, minlength=N * 2), dtype=bool)
		red = ''.join(S[r])
		blue = ''.join(S[~r])
		ret += red == blue[::-1]
	return ret
(S, T) = (S[:N], S[:N - 1:-1])
t_counts = defaultdict(int)
for choice in itertools.product([0, 1], repeat=N):
	t = ''
	rev = ''
	for (i, c) in enumerate(choice):
		t += T[i] if c else ''
		rev += '' if c else T[i]
	t_counts[t, rev] += 1
ans = 0
for choice in itertools.product([0, 1], repeat=N):
	s = ''
	rev = ''
	for (i, c) in enumerate(choice):
		s += S[i] if c else ''
		rev += '' if c else S[i]
	ans += t_counts[s, rev]
print(ans)


import sys, queue, math, copy, itertools
from fractions import gcd
sys.setrecursionlimit(10 ** 7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
LI = lambda : [int(x) for x in sys.stdin.readline().split()]
_LI = lambda : [int(x) - 1 for x in sys.stdin.readline().split()]
NI = lambda : int(sys.stdin.readline())
N = NI()
S = input()
sr = S[-1:N - 1:-1]
ans = 0
fwd = []
rev = {}
for bit in range(2 ** N):
	red1 = ''
	blue1 = ''
	red2 = ''
	blue2 = ''
	b = 1
	for i in range(N):
		if b & bit:
			red1 += S[i]
			red2 += sr[i]
		else:
			blue1 += S[i]
			blue2 += sr[i]
		b <<= 1
	fwd.append(red1 + ' ' + blue1)
	key = blue2 + ' ' + red2
	if key in rev:
		rev[key] += 1
	else:
		rev[key] = 1
for s in fwd:
	if s in rev:
		ans += rev[s]
print(ans)


n = int(input())
s = str(input())
L = s[0:n]
R = s[n:]
R = list(R)
R.reverse()
R = ''.join(R)
DL = {}
for i in range(2 ** n):
	p = ''
	q = ''
	for j in range(n):
		if i >> j & 1:
			p += L[j]
		else:
			q += L[j]
	if (p, q) in DL:
		DL[p, q] += 1
	else:
		DL[p, q] = 1
DR = {}
for i in range(2 ** n):
	p = ''
	q = ''
	for j in range(n):
		if i >> j & 1:
			p += R[j]
		else:
			q += R[j]
	if (p, q) in DR:
		DR[p, q] += 1
	else:
		DR[p, q] = 1
ans = 0
for (k, v) in DL.items():
	if k in DR:
		ans += v * DR[k]
print(ans)


from collections import defaultdict

def main():
	N = int(input())
	S = input()
	X = S[:N]
	Y = S[N:]
	Y = Y[::-1]
	dx = defaultdict(int)
	dy = defaultdict(int)
	for bit in range(1 << N):
		red = ''
		blue = ''
		for i in range(N):
			if bit & 1 << i:
				red += X[i]
			else:
				blue += X[i]
		dx[red, blue] += 1
	for bit in range(1 << N):
		red = ''
		blue = ''
		for i in range(N):
			if bit & 1 << i:
				red += Y[i]
			else:
				blue += Y[i]
		dy[red, blue] += 1
	ans = 0
	for (k, v) in dx.items():
		ans += dy[k] * v
	print(ans)
main()


from collections import defaultdict
n = int(input())
s = input()

def solve(s):
	d = defaultdict(int)
	for i in range(2 ** n):
		blue = red = ''
		for k in range(n):
			if 1 << k & i:
				blue += s[k]
			else:
				red += s[k]
		d[blue, red] += 1
	return d
left = solve(s[:n])
right = solve(s[::-1][:n])
ans = 0
for ((b, r), v) in left.items():
	ans += v * right[r, b]
print(ans)


from collections import defaultdict
N = int(input())
S = input()
S1 = S[:N]
S2 = S[::-1][:N]

def get_s(s, i):
	s1 = s2 = ''
	for j in range(N):
		if i >> j & 1:
			s1 += s[j]
		else:
			s2 += s[j]
	return (s1, s2)
d1 = defaultdict(int)
d2 = defaultdict(int)
for i in range(2 ** N):
	s1 = get_s(S1, i)
	d1[s1] += 1
	s2 = get_s(S2, i)
	d2[s2] += 1
ans = 0
for k in d1:
	ans += d1[k] * d2[k]
print(ans)


import collections
d = collections.defaultdict(int)
n = int(input())
s = input()

def f(s, r, b, t):
	if t == n:
		d[r, b] += 1
		return
	f(s, r + s[t], b, t + 1)
	f(s, r, b + s[t], t + 1)
f(s[:n], '', '', 0)
d1 = d
d = collections.defaultdict(int)
f(s[-1:n - 1:-1], '', '', 0)
ans = 0
for (i, j) in d.items():
	ans += j * d1[i]
print(ans)


from collections import defaultdict
N = int(input())
S = input()
S1 = S[:N]
S2 = S[N:][::-1]
D = defaultdict(int)
ans = 0
for i in range(2 ** N):
	bit = bin(2 ** N + i)[3:]
	red1 = ''.join([d for (d, s) in zip(S1, bit) if s == '1'])
	blue1 = ''.join([d for (d, s) in zip(S1, bit) if s == '0'])
	D[red1, blue1] += 1
for i in range(2 ** N):
	bit = bin(2 ** N + i)[3:]
	red2 = ''.join([d for (d, s) in zip(S2, bit) if s == '1'])
	blue2 = ''.join([d for (d, s) in zip(S2, bit) if s == '0'])
	ans += D[blue2, red2]
print(ans)


import itertools as I
from collections import Counter as C
n = int(input())
s = input()
l = s[:n]
r = s[n:][::-1]
a = C()
b = C()
for i in I.product([0, 1], repeat=n):
	t = u = v = w = ''
	for j in range(n):
		if i[j]:
			t += l[j]
			u += r[j]
		else:
			v += l[j]
			w += r[j]
	a[t, v] += 1
	b[u, w] += 1
print(sum((a[i] * b[i] for i in a.keys())))


n = int(input())
s = input()
hash = {}
for bit in range(1 << n):
	(red, blue) = ('', '')
	for i in range(n):
		if bit & 1 << i > 0:
			red += s[i]
		else:
			blue += s[i]
	hash[red, blue] = hash.get((red, blue), 0) + 1
t = s[n:][::-1]
cnt = 0
for bit in range(1 << n):
	(red, blue) = ('', '')
	for i in range(n):
		if bit & 1 << i > 0:
			red += t[i]
		else:
			blue += t[i]
	cnt += hash.get((blue, red), 0)
print(cnt)


from collections import Counter
N = int(input())
S = input()
(left, right) = (S[:N], S[N:][::-1])
(a, b) = (Counter(), Counter())
for i in range(2 ** N):
	t = u = v = w = ''
	for j in range(N):
		if i >> j & 1:
			t += left[j]
			u += right[j]
		else:
			v += left[j]
			w += right[j]
	a[t, v] += 1
	b[u, w] += 1
print(sum((a[t] * b[t] for t in a.keys())))


n = int(input())
s = list(input())
left = s[:n]
right = s[n:]
right.reverse()
from itertools import *
from collections import defaultdict
d = defaultdict(int)
for pro in product([0, 1], repeat=n):
	s1 = s2 = ''
	for (i, p) in enumerate(pro):
		if p == 0:
			s1 += left[i]
		else:
			s2 += left[i]
	d[s1, s2] += 1
ans = 0
for pro in product([0, 1], repeat=n):
	s1 = s2 = ''
	for (i, p) in enumerate(pro):
		if p == 0:
			s1 += right[i]
		else:
			s2 += right[i]
	ans += d[s1, s2]
print(ans)


from collections import defaultdict
N = int(input())
S = input()
T = [ord(S[i]) - 96 for i in range(N)]
U = [ord(S[i]) - 96 for i in range(2 * N - 1, N - 1, -1)]
c1 = defaultdict(int)
c2 = defaultdict(int)
for i in range(1 << N):
	(a1, a2, b1, b2) = (0, 0, 0, 0)
	for j in range(N):
		if i & 1:
			a1 = a1 * 27 + T[j]
			b1 = b1 * 27 + U[j]
		else:
			a2 = a2 * 27 + T[j]
			b2 = b2 * 27 + U[j]
		i >>= 1
	c1[a1, a2] += 1
	c2[b1, b2] += 1
ret = 0
for (k, v) in c1.items():
	ret += v * c2[k]
print(ret)


import sys
from collections import defaultdict
from itertools import combinations
sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline

def solve():
	N = int(rl())
	S = rl().rstrip()
	(s1, s2) = (S[:N], S[N:][::-1])
	l_dict = defaultdict(int)
	r_dict = defaultdict(int)
	for i in range(N + 1):
		for red_idx in combinations(range(N), i):
			(red, blue) = ('', '')
			for j in range(N):
				if j in red_idx:
					red += s1[j]
				else:
					blue += s1[j]
			l_dict[red + ' ' + blue] += 1
	for i in range(N + 1):
		for red_idx in combinations(range(N), i):
			(red, blue) = ('', '')
			for j in range(N):
				if j in red_idx:
					red += s2[j]
				else:
					blue += s2[j]
			r_dict[red + ' ' + blue] += 1
	ans = sum((l_dict[key] * r_dict[key] for key in l_dict))
	print(ans)
solve()


from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import defaultdict
from bisect import bisect

def read():
	return int(input())

def reads():
	return [int(x) for x in input().split()]
N = read()
S = input()
former = defaultdict(int)
latter = defaultdict(int)
for bits in range(1 << N):
	bs1 = []
	rs1 = []
	bs2 = []
	rs2 = []
	for i in range(N):
		if 1 << i & bits:
			rs1.append(S[i])
			rs2.append(S[-1 - i])
		else:
			bs1.append(S[i])
			bs2.append(S[-1 - i])
	former[''.join(rs1), ''.join(bs1)] += 1
	latter[''.join(bs2), ''.join(rs2)] += 1
ans = 0
for (k, v) in former.items():
	if k in latter:
		ans += v * latter[k]
print(ans)


n = int(input())
s = list(input())
l = [s[i] for i in range(n)]
r = [s[i] for i in range(n, 2 * n)]
r = r[::-1]
from collections import defaultdict
ld = defaultdict(int)
rd = defaultdict(int)
for i in range(2 ** n):
	ls = ['', '']
	rs = ['', '']
	for j in range(n):
		if (i >> j) % 2 == 0:
			ls[0] += l[j]
			rs[0] += r[j]
		elif (i >> j) % 2 == 1:
			ls[1] += l[j]
			rs[1] += r[j]
	ls = tuple(ls)
	rs = tuple(rs)
	ld[ls] += 1
	rd[rs] += 1
cnt = 0
for k in ld.keys():
	a = ld[k]
	b = rd[k]
	cnt += a * b
print(cnt)


def f():
	(n, s) = (int(input()), input())
	(a, b) = (s[n - 1::-1], s[n:])
	ad = {}
	bd = {}
	for i in range(2 ** n):
		(sa, ta, sb, tb) = ('', '', '', '')
		for j in range(n):
			if i % 2:
				sa += a[j]
				sb += b[j]
			else:
				ta += a[j]
				tb += b[j]
			i //= 2
		ad[sa, ta] = 1 if (sa, ta) not in ad else ad[sa, ta] + 1
		bd[sb, tb] = 1 if (sb, tb) not in bd else bd[sb, tb] + 1
	ans = 0
	for k in ad:
		if k in bd:
			ans += bd[k] * ad[k]
	print(ans)
f()


def i1():
	return int(input())

def i2():
	return [int(i) for i in input().split()]
n = i1()
s = input()
from collections import defaultdict
ad1 = defaultdict(int)
ad2 = defaultdict(int)
for i in range(1 << n):
	a = ''
	b = ''
	for j in range(n):
		if i & 1 << j == 0:
			a += s[j]
		else:
			b += s[j]
	ad1[a + '_' + b[::-1]] += 1
	a = ''
	b = ''
	for j in range(n):
		if i & 1 << j:
			a += s[j + n]
		else:
			b += s[j + n]
	ad2[b[::-1] + '_' + a] += 1
cc = 0
for i in ad1.keys():
	cc += ad1[i] * ad2[i]
print(cc)


import sys

def I():
	return int(sys.stdin.readline().rstrip())

def LS2():
	return list(sys.stdin.readline().rstrip())
N = I()
S = LS2()
ans = 0
left = []
right = []
for i in range(2 ** N):
	red = []
	blue = []
	for j in range(N):
		if i >> j & 1:
			red.append(S[j])
		else:
			blue.append(S[j])
	red = ''.join(red)
	blue = ''.join(blue)
	left.append((red, blue))
for i in range(2 ** N):
	red = []
	blue = []
	for j in range(N):
		if i >> j & 1:
			red.append(S[j + N])
		else:
			blue.append(S[j + N])
	(red, blue) = (blue, red)
	red.reverse()
	blue.reverse()
	red = ''.join(red)
	blue = ''.join(blue)
	right.append((red, blue))
from operator import itemgetter
right = sorted(right, key=itemgetter(0, 1))
from bisect import bisect_left, bisect
ans = 0
for i in range(2 ** N):
	ans += bisect(right, left[i]) - bisect_left(right, left[i])
print(ans)


import sys
sys.setrecursionlimit(4100000)
import math
import itertools
INF = float('inf')
from heapq import heapify, heappop, heappush

def main():
	n = int(input())
	S = input()
	l_dict = {}
	r_dict = {}
	L = S[:n]
	R = S[n:]
	for i in range(2 ** n):
		(lr, lb, rr, rb) = ('', '', '', '')
		for j in range(n):
			if i >> j & 1:
				lr += L[j]
				rr += R[j]
			else:
				lb += L[j]
				rb += R[j]
		rr = rr[::-1]
		rb = rb[::-1]
		if l_dict.get((lr, lb)):
			l_dict[lr, lb] += 1
		else:
			l_dict[lr, lb] = 1
		if r_dict.get((rb, rr)):
			r_dict[rb, rr] += 1
		else:
			r_dict[rb, rr] = 1
	ans = 0
	for (k, v) in l_dict.items():
		if k in r_dict:
			ans += v * r_dict[k]
	print(ans)
main()


from collections import defaultdict
N = int(input())
S = input()
countp = defaultdict(int)
counts = defaultdict(int)
prefix = S[:N]
suffix = S[2 * N - 1:N - 1:-1]
for i in range(1 << N - 1):
	p1 = ''
	s1 = ''
	p2 = ''
	s2 = ''
	for j in range(N):
		if 1 << j & i:
			p1 += prefix[j]
			s1 += suffix[j]
		else:
			p2 += prefix[j]
			s2 += suffix[j]
	countp[p1, p2] += 1
	countp[p2, p1] += 1
	counts[s1, s2] += 1
	counts[s2, s1] += 1
ans = 0
for (k, v) in countp.items():
	ans += v * counts[k]
print(ans)


import sys
input = sys.stdin.readline
from collections import defaultdict

def main():
	n = int(input())
	s = input().strip()
	pc = defaultdict(lambda : 0)
	for i in range(pow(2, n)):
		rd = ''
		bl = ''
		for b in range(n):
			if i // pow(2, b) % 2 == 1:
				rd += s[b]
			else:
				bl += s[b]
		pc[rd, bl] += 1
	ans = 0
	s = s[::-1]
	for i in range(pow(2, n)):
		rd = ''
		bl = ''
		for b in range(n):
			if i // pow(2, b) % 2 == 1:
				bl += s[b]
			else:
				rd += s[b]
		ans += pc[rd, bl]
	print(ans)
main()


import sys
input = sys.stdin.readline
from collections import Counter
N = int(input())
S = input().rstrip()
left = [('', '')]
for s in S[:N]:
	left = [(x[0] + s, x[1]) for x in left] + [(x[0], x[1] + s) for x in left]
left = [x + ' ' + y for (x, y) in left]
counter_L = Counter(left)
right = [('', '')]
for s in S[N:][::-1]:
	right = [(x[0] + s, x[1]) for x in right] + [(x[0], x[1] + s) for x in right]
right = [x + ' ' + y for (x, y) in right]
answer = sum((counter_L[s] for s in right))
print(answer)


import sys, bisect, string, math, time, functools, random, fractions
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
from itertools import permutations, combinations, groupby
rep = range
R = range

def Golf():
	(n, *t) = map(int, open(0).read().split())

def I():
	return int(input())

def S_():
	return input()

def IS():
	return input().split()

def LS():
	return [i for i in input().split()]

def MI():
	return map(int, input().split())

def LI():
	return [int(i) for i in input().split()]

def LI_():
	return [int(i) - 1 for i in input().split()]

def NI(n):
	return [int(input()) for i in range(n)]

def NI_(n):
	return [int(input()) - 1 for i in range(n)]

def NLI(n):
	return [[int(i) for i in input().split()] for i in range(n)]

def NLI_(n):
	return [[int(i) - 1 for i in input().split()] for i in range(n)]

def StoLI():
	return [ord(i) - 97 for i in input()]

def ItoS(n):
	return chr(n + 97)

def LtoS(ls):
	return ''.join([chr(i + 97) for i in ls])

def RA():
	return map(int, open(0).read().split())

def RLI(n=8, a=1, b=10):
	return [random.randint(a, b) for i in range(n)]

def RI(a=1, b=10):
	return random.randint(a, b)

def Rtest(T):
	(case, err) = (0, 0)
	for i in range(T):
		inp = INP()
		(a1, ls) = naive(*inp)
		a2 = solve(*inp)
		if a1 != a2:
			print((a1, a2), inp)
			err += 1
		case += 1
	print('Tested', case, 'case with', err, 'errors')

def GI(V, E, ls=None, Directed=False, index=1):
	org_inp = []
	g = [[] for i in range(V)]
	FromStdin = True if ls == None else False
	for i in range(E):
		if FromStdin:
			inp = LI()
			org_inp.append(inp)
		else:
			inp = ls[i]
		if len(inp) == 2:
			(a, b) = inp
			c = 1
		else:
			(a, b, c) = inp
		if index == 1:
			a -= 1
			b -= 1
		aa = (a, c)
		bb = (b, c)
		g[a].append(bb)
		if not Directed:
			g[b].append(aa)
	return (g, org_inp)

def GGI(h, w, search=None, replacement_of_found='.', mp_def={'#': 1, '.': 0}, boundary=1):
	mp = [boundary] * (w + 2)
	found = {}
	for i in R(h):
		s = input()
		for char in search:
			if char in s:
				found[char] = (i + 1) * (w + 2) + s.index(char) + 1
				mp_def[char] = mp_def[replacement_of_found]
		mp += [boundary] + [mp_def[j] for j in s] + [boundary]
	mp += [boundary] * (w + 2)
	return (h + 2, w + 2, mp, found)

def TI(n):
	return GI(n, n - 1)

def accum(ls):
	rt = [0]
	for i in ls:
		rt += [rt[-1] + i]
	return rt

def bit_combination(n, base=2):
	rt = []
	for tb in R(base ** n):
		s = [tb // base ** bt % base for bt in R(n)]
		rt += [s]
	return rt

def gcd(x, y):
	if y == 0:
		return x
	if x % y == 0:
		return y
	while x % y != 0:
		(x, y) = (y, x % y)
	return y

def YN(x):
	print(['NO', 'YES'][x])

def Yn(x):
	print(['No', 'Yes'][x])

def show(*inp, end='\n'):
	if show_flg:
		print(*inp, end=end)
mo = 10 ** 9 + 7
inf = float('inf')
FourNb = [(-1, 0), (1, 0), (0, 1), (0, -1)]
EightNb = [(-1, 0), (1, 0), (0, 1), (0, -1), (1, 1), (-1, -1), (1, -1), (-1, 1)]
compas = dict(zip('WENS', FourNb))
cursol = dict(zip('LRUD', FourNb))
l_alp = string.ascii_lowercase
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
input = lambda : sys.stdin.readline().rstrip()
show_flg = False
show_flg = True
ans = 0
n = I()
s = input()
a = s[:n]
b = s[n:][::-1]

def coloring(x):
	N = 1 << n
	dc = defaultdict(int)
	for i in range(N):
		r = ''
		b = ''
		for j in range(n):
			if i >> j & 1:
				r += x[j]
			else:
				b += x[j]
		dc[r + '-' + b] += 1
	return dc
fd = coloring(a)
ld = coloring(b)
for (i, j) in fd.items():
	ans += ld[i] * j
print(ans)


from collections import defaultdict
from itertools import combinations

def solve():
	N = int(input())
	S = input()
	(s1, s2) = (S[:N], S[N:][::-1])
	l_dict = defaultdict(int)
	r_dict = defaultdict(int)
	for i in range(N + 1):
		for red_idx in combinations(range(N), i):
			(red, blue) = ('', '')
			for j in range(N):
				if j in red_idx:
					red += s1[j]
				else:
					blue += s1[j]
			l_dict[red + ' ' + blue] += 1
	for i in range(N + 1):
		for red_idx in combinations(range(N), i):
			(red, blue) = ('', '')
			for j in range(N):
				if j in red_idx:
					red += s2[j]
				else:
					blue += s2[j]
			r_dict[red + ' ' + blue] += 1
	ans = sum((l_dict[key] * r_dict[key] for key in l_dict))
	print(ans)
solve()


def main(n, a):
	(a1, a2) = (a[:n], a[n:])
	a2.reverse()
	d1 = {}
	d2 = {}
	for i in range(2 ** n):
		r1 = []
		r2 = []
		l1 = []
		l2 = []
		for j in range(n):
			if i >> j & 1:
				r1.append(a1[j])
				r2.append(a2[j])
			else:
				l1.append(a1[j])
				l2.append(a2[j])
		s1 = ''.join(r1) + '-' + ''.join(l1)
		s2 = ''.join(r2) + '-' + ''.join(l2)
		if s1 in d1:
			d1[s1] += 1
		else:
			d1[s1] = 1
		if s2 in d2:
			d2[s2] += 1
		else:
			d2[s2] = 1
	ans = 0
	for k in d1:
		if k in d2:
			ans += d1[k] * d2[k]
	return ans
n = int(input())
a = list(input())
print(main(n, a))


from collections import Counter
n = int(input())
s = input().rstrip()
front = s[:n]
back = s[n:]
back = list(reversed(back))
front_cnt = Counter()
back_cnt = Counter()
for i in range(2 ** n):
	fred = fblue = bred = bblue = ''
	for j in range(n):
		if i & 1 << j:
			fred += front[j]
			bred += back[j]
		else:
			fblue += front[j]
			bblue += back[j]
	front_cnt[fred + '_' + fblue] += 1
	back_cnt[bred + '_' + bblue] += 1
ans = 0
for key in front_cnt.keys():
	ans += front_cnt[key] * back_cnt[key]
print(ans)


from itertools import product, compress
N = int(input())
Ss = input()
Fss = [list(compress(Ss[:N], sels))[::-1] for sels in product([0, 1], repeat=N)]
ans = 0
for iFs in range(2 ** N):
	Fs = Fss[iFs]
	Gs = Fss[2 ** N - 1 - iFs]
	lenF = len(Fs)
	lenG = N - lenF
	dp = [1] + [0] * lenF
	for (i, s) in enumerate(Ss[N:]):
		dp2 = [0] * (lenF + 1)
		for j in range(lenF + 1):
			if dp[j] == 0:
				continue
			if j < lenF and s == Fs[j]:
				dp2[j + 1] += dp[j]
			if 0 <= i - j < lenG and s == Gs[i - j]:
				dp2[j] += dp[j]
		dp = dp2
	ans += dp[lenF]
print(ans)


n = int(input())
s = input()
left = {}
right = {}
sl = s[:n]
sr = s[n:]
for i in range(1 << n):
	lr = lb = ''
	rr = rb = ''
	for j in range(n):
		if i & 1 << j:
			lr += sl[j]
			rr += sr[j]
		else:
			lb += sl[j]
			rb += sr[j]
	l = lr + ',' + lb
	r = (rr + ',' + rb)[::-1]
	if l in left:
		left[l] += 1
	else:
		left[l] = 1
	if r in right:
		right[r] += 1
	else:
		right[r] = 1
ans = 0
for i in left:
	if i in right:
		ans += left[i] * right[i]
print(ans)


from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import defaultdict
from bisect import bisect

def read():
	return int(input())

def reads():
	return [int(x) for x in input().split()]
N = read()
S = input()
ans = 0
for bits in range(2 ** N):
	bs = []
	rs = []
	for i in range(N):
		if 1 << i & bits == 0:
			rs.append(S[i])
		else:
			bs.append(S[i])
	rs.reverse()
	bs.reverse()
	lenr = len(rs)
	lenb = len(bs)
	dp = [[0] * (lenb + 1) for _ in range(lenr + 1)]
	dp[0][0] = 1
	for i in range(lenr + 1):
		for j in range(lenb + 1):
			if i < lenr and rs[i] == S[N + i + j]:
				dp[i + 1][j] += dp[i][j]
			if j < lenb and bs[j] == S[N + i + j]:
				dp[i][j + 1] += dp[i][j]
	ans += dp[-1][-1]
print(ans)


from collections import Counter
n = int(input())
s = input()
l = Counter()
for i in range(2 ** n):
	(r, b) = ([], [])
	for j in range(n):
		if i >> j & 1:
			r.append(s[j])
		else:
			b.append(s[j])
	r = ''.join(r)
	b = ''.join(b)
	l[r[::-1], b[::-1]] += 1
ans = 0
for i in range(2 ** n):
	(r, b) = ([], [])
	for j in range(n):
		if i >> j & 1:
			r.append(s[n + j])
		else:
			b.append(s[n + j])
	r = ''.join(r)
	b = ''.join(b)
	ans += l[b, r]
print(ans)


N = int(input())
S = input()
SL = S[:N]
SR = S[N:]
SR = SR[::-1]
MR = {}
ans = 0
for i in range(2 ** N):
	R = ''
	B = ''
	for j in range(N):
		if i % 2:
			R += SL[j]
		else:
			B += SL[j]
		i //= 2
	if R + '_' + B in MR:
		MR[R + '_' + B] += 1
	else:
		MR[R + '_' + B] = 1
for i in range(2 ** N):
	R = ''
	B = ''
	for j in range(N):
		if i % 2:
			R += SR[j]
		else:
			B += SR[j]
		i //= 2
	if R + '_' + B in MR:
		ans += MR[R + '_' + B]
print(ans)


n = int(input())
s = list(input())
l = s[:n]
r = list(reversed(s[n:]))
hashl = {}
hashr = {}
for i in range(1 << n):
	llr = []
	llb = []
	lrr = []
	lrb = []
	for k in range(n):
		if i & 1 << k:
			llr.append(l[k])
			lrr.append(r[k])
		else:
			llb.append(l[k])
			lrb.append(r[k])
	sl = (''.join(llr), ''.join(llb))
	sr = (''.join(lrr), ''.join(lrb))
	if sl not in hashl:
		hashl[sl] = 1
	else:
		hashl[sl] += 1
	if sr not in hashr:
		hashr[sr] = 1
	else:
		hashr[sr] += 1
ret = 0
for (strpair, c) in hashl.items():
	if strpair in hashr:
		ret += hashr[strpair] * c
print(ret)


N = int(input())
S = input()
S_l = S[:N]
S_r = S[N:][::-1]
dict_l = {}
dict_r = {}
ans = 0
for num in range(2 ** N):
	tmpl_1 = ''
	tmpl_2 = ''
	tmpr_1 = ''
	tmpr_2 = ''
	for n in range(N):
		if num >> N - 1 - n & 1:
			tmpl_1 += S_l[n]
			tmpr_1 += S_r[n]
		else:
			tmpl_2 += S_l[n]
			tmpr_2 += S_r[n]
	dict_l[tmpl_1 + '_' + tmpl_2] = dict_l.get(tmpl_1 + '_' + tmpl_2, 0) + 1
	dict_r[tmpr_1 + '_' + tmpr_2] = dict_r.get(tmpr_1 + '_' + tmpr_2, 0) + 1
for (k, v) in dict_l.items():
	ans += v * dict_r.get(k, 0)
print(ans)


from collections import Counter
N = int(input())
S = input()
S_former = S[:N]
S_latter = S[N:][::-1]
ans = 0

def analyzer(St):
	n = len(St)
	A = []
	for i in range(2 ** n):
		red = ''
		blue = ''
		for j in range(n):
			if i >> j & 1 == 1:
				red += St[j]
			else:
				blue += St[j]
		A.append((red, blue))
	return Counter(A)
SC_former = analyzer(S_former)
SC_latter = analyzer(S_latter)
for (ke, va) in SC_former.items():
	ans += SC_latter[ke] * va
print(ans)


N = int(input())
S = input()
(S, T) = (S[:N], S[N:][::-1])
A = dict()
B = dict()
(X1, Y1, X2, Y2, Z) = (0, 0, 0, 0, 0)
for i in range(1 << N):
	(X1, Y1, X2, Y2, Z) = ('', '', '', '', 1)
	for j in range(N):
		if i & Z:
			X1 += S[j]
			X2 += T[j]
		else:
			Y1 += S[j]
			Y2 += T[j]
		Z <<= 1
	A[X1, Y1] = A.get((X1, Y1), 0) + 1
	B[X2, Y2] = B.get((X2, Y2), 0) + 1
P = 0
Z = list(A.keys())
for i in range(len(Z)):
	P += A[Z[i]] * B.get(Z[i], 0)
print(P)


from collections import defaultdict
N = int(input())
S = input()
cnt_left = defaultdict(int)
for i in range(2 ** N):
	(a, b) = ('', '')
	for j in range(N):
		if i >> j & 1:
			a += S[j]
		else:
			b += S[j]
	cnt_left[a, b] += 1
S = S[::-1]
cnt_right = defaultdict(int)
for i in range(2 ** N):
	(a, b) = ('', '')
	for j in range(N):
		if i >> j & 1:
			a += S[j]
		else:
			b += S[j]
	cnt_right[a, b] += 1
answer = 0
for k in cnt_left.keys():
	answer += cnt_left[k] * cnt_right[k]
print(answer)


N = int(input())
S = input()
ans = 0
first = {}
last = {}

def dfs(r, b, num):
	if num == N:
		if (r, b) not in first:
			first[r, b] = 0
		first[r, b] += 1
		return 0
	if len(r) < N:
		dfs(r + S[num], b, num + 1)
	if len(b) < N:
		dfs(r, S[num] + b, num + 1)
dfs('', '', 0)

def dfs2(r, b, num):
	if num == 2 * N:
		if (r, b) not in last:
			last[r, b] = 0
		last[r, b] += 1
		return 0
	if len(r) < N:
		dfs2(r + S[num], b, num + 1)
	if len(b) < N:
		dfs2(r, S[num] + b, num + 1)
dfs2('', '', N)
for (r, b) in first:
	if (b, r) in last:
		ans += first[r, b] * last[b, r]
print(ans)


from collections import defaultdict
N = int(input())
S = input()
(A, B) = (S[:N], S[N:])
D = defaultdict(int)
ans = 0

def paint(X, i):
	r = ''
	b = ''
	for (j, k) in enumerate(format(i, 'b').zfill(N)):
		if k == '1':
			r += X[j]
		else:
			b += X[j]
	return (r, b)
for i in range(2 ** N):
	(r, b) = paint(A, i)
	D[r, b] += 1
for i in range(2 ** N):
	(r, b) = paint(B, i)
	ans += D[b[::-1], r[::-1]]
print(ans)


N = int(input())
S = input()
T1 = S[:N]
T2 = S[N:][::-1]

def window(i, P, L):
	if i == N:
		L.append(P)
		return L
	L = window(i + 1, P + [0], L)
	L = window(i + 1, P + [1], L)
	return L
L = window(0, [], [])
dic1 = {}
dic2 = {}
for mask in L:
	k1 = ''
	k2 = ''
	r1 = ''
	r2 = ''
	for i in range(N):
		if mask[i]:
			k1 += T1[i]
			k2 += T2[i]
		else:
			r1 += T1[i]
			r2 += T2[i]
	c1 = k1 + '_' + r1
	c2 = k2 + '_' + r2
	if not c1 in dic1.keys():
		dic1[c1] = 1
	else:
		dic1[c1] += 1
	if not c2 in dic2.keys():
		dic2[c2] = 1
	else:
		dic2[c2] += 1
ans = 0
for (k1, v1) in dic1.items():
	if k1 in dic2.keys():
		ans += dic2[k1] * v1
print(ans)


from itertools import product
N = int(input())
S = input()
r = [0, 1]
ans = 0
d = [{} for i in range(N + 1)]
for p in product(r, repeat=N):
	s = []
	for i in range(N):
		if p[i]:
			s.append(S[i])
	for i in range(N - 1, -1, -1):
		if p[i] == 0:
			s.append(S[i])
	l = sum(p)
	s = ''.join(s)
	d[l][s] = d[l].get(s, 0) + 1
for p in product(r, repeat=N):
	s = []
	for i in range(N - 1, -1, -1):
		if p[i]:
			s.append(S[i + N])
	for i in range(N):
		if p[i] == 0:
			s.append(S[i + N])
	l = sum(p)
	s = ''.join(s)
	ans += d[l].get(s, 0)
print(ans)


from itertools import product
from collections import defaultdict

def solve(S):

	def helper(s):
		n = len(s)
		d = defaultdict(int)
		for p in product((True, False), repeat=n):
			t = [-1] * (n + 1)
			t[-1] = sum(p)
			i = 0
			j = n - 1
			for (c, f) in zip(s, p):
				if f:
					t[i] = c
					i += 1
				else:
					t[j] = c
					j -= 1
			d[tuple(t)] += 1
		return d
	S = [ord(c) - ord('a') for c in S]
	n = len(S) // 2
	d1 = helper(S[:n])
	d2 = helper(S[:n - 1:-1])
	res = 0
	for (k, c) in d1.items():
		res += c * d2[k]
	return res
N = int(input())
S = input()
print(solve(S))


import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce, lru_cache

def input():
	return sys.stdin.readline().strip()

def INT():
	return int(input())

def MAP():
	return map(int, input().split())

def LIST():
	return list(map(int, input().split()))

def TUPLE():
	return tuple(map(int, input().split()))

def ZIP(n):
	return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
from decimal import *
N = INT()
S = input()
s1 = []
dic_s2 = defaultdict(int)
for x in product([0, 1], repeat=N):
	s1_red = ''
	s1_blue = ''
	s2_red = ''
	s2_blue = ''
	for i in range(N):
		if x[i]:
			s1_red += S[i]
			s2_red += S[N + i]
		else:
			s1_blue += S[i]
			s2_blue += S[N + i]
	s1.append((s1_red, s1_blue))
	dic_s2[s2_blue[::-1], s2_red[::-1]] += 1
ans = 0
for x in s1:
	ans += dic_s2[x]
print(ans)


N = int(input())
S = list(input())
S1 = S[:N]
S2 = S[2 * N - 1:N - 1:-1]
dict_1 = dict()
q_list = [''] * 2 ** N
res = 0
for i in range(2 ** N):
	sb = bin(2 ** N + i)[3:]
	red = []
	blue = []
	red2 = []
	blue2 = []
	for j in range(N):
		if sb[j] == '0':
			red.append(S1[j])
			red2.append(S2[j])
		else:
			blue.append(S1[j])
			blue2.append(S2[j])
	sss = ''.join(red + ['|'] + blue)
	sss2 = ''.join(red2 + ['|'] + blue2)
	if sss not in dict_1.keys():
		dict_1[sss] = 1
	else:
		dict_1[sss] += 1
	q_list[i] = sss2
for q in q_list:
	res += dict_1.get(q, 0)
print(res)


from collections import deque

def comb(s):
	p = deque([('', '')])
	for i in range(len(s)):
		for j in range(2 ** i):
			e = p.pop()
			p.appendleft((e[0] + s[i], e[1]))
			p.appendleft((e[0], e[1] + s[i]))
	return p
n = int(input())
s = input()
sl = s[0:n]
sr = s[n:2 * n][::-1]
keys1 = [c[0] + '-' + c[1] for c in comb(sl)]
keys2 = [c[0] + '-' + c[1] for c in comb(sr)]
dict = {}
for key1 in keys1:
	if key1 in dict:
		dict[key1] += 1
	else:
		dict[key1] = 1
cnt = 0
for key2 in keys2:
	if key2 in dict:
		cnt += dict[key2]
print(cnt)


import sys
sys.setrecursionlimit(10 ** 6)

def main():
	n = int(input())
	s = input()
	dic = {}
	for i in range(0, 2 ** n):
		temp = bin(i)[2:].zfill(n)
		ts1 = ''
		ts2 = ''
		for j in range(n):
			if temp[j] == '1':
				ts1 += s[j]
			else:
				ts2 += s[j]
		if (ts1, ts2) in dic.keys():
			dic[ts1, ts2] += 1
		else:
			dic.update({(ts1, ts2): 1})
	ans = 0
	s = s[::-1]
	for i in range(0, 2 ** n):
		temp = bin(i)[2:].zfill(n)
		ts1 = ''
		ts2 = ''
		for j in range(n):
			if temp[j] == '1':
				ts1 += s[j]
			else:
				ts2 += s[j]
		if (ts1, ts2) in dic.keys():
			ans += dic[ts1, ts2]
	print(ans)
main()


from collections import defaultdict
import sys

def input():
	return sys.stdin.readline().rstrip()

def I():
	return int(input())

def S():
	return input()
n = I()
s = S()
sa = s[:n]
sb = s[n:][::-1]
A = defaultdict(int)
B = defaultdict(int)
for bit in range(1 << n):
	red_A = []
	red_B = []
	blue_A = []
	blue_B = []
	for i in range(n):
		if bit & 1 << i:
			red_A.append(sa[i])
			blue_B.append(sb[i])
		else:
			blue_A.append(sa[i])
			red_B.append(sb[i])
	a_key = ''.join(red_A) + ',' + ''.join(blue_A)
	b_key = ''.join(blue_B) + ',' + ''.join(red_B)
	A[a_key] += 1
	B[b_key] += 1
ans = 0
for key in A.keys():
	if key in B:
		ans += A[key] * B[key]
print(ans)


import sys
sys.setrecursionlimit(10 ** 7)

def I():
	return int(sys.stdin.readline().rstrip())

def MI():
	return map(int, sys.stdin.readline().rstrip().split())

def LI():
	return list(map(int, sys.stdin.readline().rstrip().split()))

def LI2():
	return list(map(int, sys.stdin.readline().rstrip()))

def S():
	return sys.stdin.readline().rstrip()

def LS():
	return list(sys.stdin.readline().rstrip().split())

def LS2():
	return list(sys.stdin.readline().rstrip())
N = I()
S = LS2()
from collections import defaultdict
d_left = defaultdict(int)
d_right = defaultdict(int)
for i in range(2 ** N):
	left_red = ''
	left_blue = ''
	right_red = ''
	right_blue = ''
	for j in range(N):
		if i >> j & 1:
			left_red += S[j]
		else:
			left_blue += S[j]
	for j in range(2 * N - 1, N - 1, -1):
		if i >> j - N & 1:
			right_red += S[j]
		else:
			right_blue += S[j]
	d_left[left_red, left_blue] += 1
	d_right[right_red, right_blue] += 1
ans = 0
for key in d_left.keys():
	ans += d_left[key] * d_right[key]
print(ans)


from collections import defaultdict
(N, S) = open(0).read().split()
N = int(N)
ldic = defaultdict(int)
rdic = defaultdict(int)
L = S[:N]
R = S[N:][::-1]
for i in range(2 ** N):
	la = ''
	lb = ''
	ra = ''
	rb = ''
	for j in range(N):
		if i % 2 == 1:
			la += L[j]
			ra += R[j]
		else:
			lb += L[j]
			rb += R[j]
		i >>= 1
	ldic[la, lb] += 1
	rdic[ra, rb] += 1
ans = sum((rdic[k] * ldic[k] for k in ldic.keys()))
print(ans)


from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, cos, radians, pi, sin
from operator import mul
from functools import reduce
from operator import mul
sys.setrecursionlimit(2147483647)
INF = 10 ** 13

def LI():
	return list(map(int, sys.stdin.buffer.readline().split()))

def I():
	return int(sys.stdin.buffer.readline())

def LS():
	return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()

def S():
	return sys.stdin.buffer.readline().rstrip().decode('utf-8')

def IR(n):
	return [I() for i in range(n)]

def LIR(n):
	return [LI() for i in range(n)]

def SR(n):
	return [S() for i in range(n)]

def LSR(n):
	return [LS() for i in range(n)]

def SRL(n):
	return [list(S()) for i in range(n)]

def MSRL(n):
	return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7
n = I()
s = S()
s1 = s[:n]
s2 = s[n:][::-1]
D1 = defaultdict(int)
D2 = defaultdict(int)
for i in range(2 ** n):
	a1 = ''
	b1 = ''
	for j in range(n):
		if i >> j & 1:
			a1 += s1[j]
		else:
			b1 += s1[j]
	D1[a1, b1] += 1
for i in range(2 ** n):
	a2 = ''
	b2 = ''
	for j in range(n):
		if i >> j & 1:
			a2 += s2[j]
		else:
			b2 += s2[j]
	D2[a2, b2] += 1
ret = 0
for i in D1:
	ret += D1[i] * D2[i]
print(ret)


N = int(input())
S = input()

def count(s):
	res = {}
	for i in range(2 ** N):
		t1 = ''
		t2 = ''
		for j in range(N):
			if i & 1 << j:
				t1 += s[j]
			else:
				t2 += s[j]
		k = t1 + t2 + 'abcdefghijklmnoprst'[bin(i).count('1')]
		res[k] = res.get(k, 0) + 1
	return res
h1 = count(S[:N])
h2 = count(S[N:][::-1])
ans = 0
for (k, v) in h1.items():
	if k in h2:
		ans += v * h2[k]
print(ans)


from collections import defaultdict
n = int(input())
s = input()
ls = s[:n]
rs = s[:n - 1:-1]
d = defaultdict(int)

def full_research(sa, r, b, t):
	if t == n:
		d[r, b] += 1
		return
	full_research(sa, r + sa[t], b, t + 1)
	full_research(sa, r, b + sa[t], t + 1)
full_research(ls, '', '', 0)
dl = d
d = defaultdict(int)
full_research(rs, '', '', 0)
ans = 0
for (dlk, dlv) in dl.items():
	ans += dlv * d[dlk]
print(ans)


N = int(input())
S = list(input())
left = S[:N]
right = S[N:][::-1]
ans = 0
for i in range(2 ** N):
	red = []
	blue = []
	for j in range(N):
		if i >> j & 1 == 1:
			red.append(S[j])
		else:
			blue.append(S[j])
	L = len(red)
	if L == 0 or L == N:
		if right == left:
			ans += 1
		continue
	dp = [[0] * L for _ in range(N)]
	zero = 0
	if right[0] == red[0]:
		dp[0][0] = 1
	if right[0] == blue[0]:
		zero = 1
	for j in range(1, N):
		if right[j] == red[0]:
			dp[j][0] = zero
		if j - 1 + L < N and right[j] == blue[j - 1]:
			dp[j][0] += dp[j - 1][0]
		if j + L < N and right[j] == blue[j]:
			zero *= 1
		else:
			zero = 0
		for k in range(1, min(j + 1, len(red))):
			if right[j] == red[k]:
				dp[j][k] += dp[j - 1][k - 1]
			if j - k <= N - L and right[j] == blue[j - k - 1]:
				dp[j][k] += dp[j - 1][k]
	ans += dp[N - 1][-1]
print(ans)


from itertools import combinations
N = int(input())
S = list(input())
L = S[:N]
R = S[:2 * N][::-1]
digit = '0' + str(N) + 'b'
LDic = {}
for i in range(2 ** N):
	pattern = format(i, digit)
	red = []
	blue = []
	for i in range(N):
		if pattern[i] == '1':
			red.append(L[i])
		else:
			blue.append(L[i])
	red = ''.join(red)
	blue = ''.join(blue)
	key = ','.join([red, blue])
	if key in LDic:
		LDic[key] += 1
	else:
		LDic[key] = 1
RDic = {}
for i in range(2 ** N):
	pattern = format(i, digit)
	red = []
	blue = []
	for i in range(N):
		if pattern[i] == '1':
			red.append(R[i])
		else:
			blue.append(R[i])
	red = ''.join(red)
	blue = ''.join(blue)
	key = ','.join([blue, red])
	if key in RDic:
		RDic[key] += 1
	else:
		RDic[key] = 1
ans = 0
for (k, v) in LDic.items():
	if k in RDic:
		ans += v * RDic[k]
print(ans)


import sys
from collections import defaultdict

def main():
	N = int(input())
	S = input()
	(mae, usi) = (S[:N], S[N:][::-1])
	(md, ud) = (defaultdict(int), defaultdict(int))
	for i in range(1 << N):
		(mr, mb, ur, ub) = ('', '', '', '')
		for j in range(N):
			if i >> j & 1:
				mr += mae[j]
				ur += usi[j]
			else:
				mb += mae[j]
				ub += usi[j]
		md[mr, mb] += 1
		ud[ur, ub] += 1
	ans = 0
	for (key, val) in md.items():
		ans += ud[key] * val
	print(ans)
main()


def run(n, s):
	sl = s[0:n]
	sr = s[n:2 * n][::-1]
	dic = {}
	keys = []
	cnt = 0
	for i in range(2 ** n):
		(red, blue, red2, blue2) = ('', '', '', '')
		bits = bin(2 ** n + i)[3:]
		for j in range(n):
			if bits[j] == '0':
				red += sl[j]
				red2 += sr[j]
			else:
				blue += sl[j]
				blue2 += sr[j]
		keys.append(red2 + '-' + blue2)
		key = red + '-' + blue
		if key not in dic.keys():
			dic[key] = 1
		else:
			dic[key] += 1
	for key in keys:
		cnt += dic.get(key, 0)
	return cnt

def read_line():
	n = int(input())
	s = input()
	return (n, s)

def main():
	(n, s) = read_line()
	print(run(n, s))
main()


N = int(input())
S = input()
first = S[:N]
latter = S[N:][::-1]
dic = {}
digit = '0' + str(N) + 'b'
for i in range(2 ** N):
	pattern = list(format(i, digit))
	red = []
	blue = []
	for j in range(N):
		if pattern[j] == '1':
			red.append(first[j])
		else:
			blue.append(first[j])
	key = ','.join((''.join(red), ''.join(blue)))
	if key in dic:
		dic[key] += 1
	else:
		dic[key] = 1
ans = 0
for i in range(2 ** N):
	pattern = list(format(i, digit))
	red = []
	blue = []
	for j in range(N):
		if pattern[j] == '1':
			red.append(latter[j])
		else:
			blue.append(latter[j])
	key = ','.join((''.join(red), ''.join(blue)))
	if key in dic:
		ans += dic[key]
print(ans)


from collections import defaultdict
n = int(input())
S = input()
A = S[:n]
B = S[n:][::-1]
Da = defaultdict(int)
Db = defaultdict(int)
ans = 0
for i in range(2 ** n):
	(a1, a2) = ('', '')
	for j in range(n):
		if i >> j & 1:
			a1 += A[j]
		else:
			a2 += A[j]
	Da[a1, a2] += 1
for i in range(2 ** n):
	(b1, b2) = ('', '')
	for j in range(n):
		if i >> j & 1:
			b1 += B[j]
		else:
			b2 += B[j]
	Db[b1, b2] += 1
for k in Da:
	ans += Da[k] * Db[k]
print(ans)


from collections import defaultdict
import sys
input = sys.stdin.readline
N = int(input())
S = input().rstrip()
ans = 0
cnt = defaultdict(int)
for bit in range(1 << N):
	a = b = ''
	for i in range(N):
		if bit >> i & 1:
			a += S[i]
		else:
			b += S[i]
	cnt[a, b] += 1
ans = 0
for bit in range(1 << N):
	a = b = ''
	for i in range(N):
		if bit >> i & 1:
			a += S[N + i]
		else:
			b += S[N + i]
	ans += cnt[b[::-1], a[::-1]]
print(ans)


N = int(input())
S = input()
S = S[:N] + S[N:][::-1]
import collections

def count(S):
	n = len(S)
	T = []
	for i in range(2 ** n):
		(r, b) = ('', '')
		for j in range(n):
			if i >> j & 1:
				r += S[j]
			else:
				b += S[j]
		T.append((r, b))
	return collections.Counter(T)
A = count(S[:N])
B = count(S[N:])
ans = 0
for a in A:
	if a in B:
		ans += A[a] * B[a]
print(ans)


n = int(input())
s = input()
s1 = s[:n]
s2 = s[n:][::-1]
dic1 = {}
dic2 = {}
for i in range(2 ** n):
	r1 = ''
	r2 = ''
	b1 = ''
	b2 = ''
	flag = format(i, 'b')
	l = len(flag)
	if l != n:
		flag = '0' * (n - l) + flag
	for j in range(n):
		if flag[j] == '0':
			r1 += s1[j]
			r2 += s2[j]
		else:
			b1 += s1[j]
			b2 += s2[j]
	if (r1, b1) not in dic1:
		dic1[r1, b1] = 1
	else:
		dic1[r1, b1] += 1
	if (r2, b2) not in dic2:
		dic2[r2, b2] = 1
	else:
		dic2[r2, b2] += 1
ans = 0
for i in dic1.keys():
	if i in dic2:
		ans += dic1[i] * dic2[i]
print(ans)


from collections import defaultdict
N = int(input())
S = input()
SL = S[:N]
SR = S[N:][::-1]
ans = 0
memo = defaultdict(int)
for bit in range(1 << N):
	red = ''
	blue = ''
	for i in range(N):
		if bit & 1 << i:
			red += SL[i]
		else:
			blue += SL[i]
	memo[red, blue] += 1
for bit in range(1 << N):
	red = ''
	blue = ''
	for i in range(N):
		if bit & 1 << i:
			red += SR[i]
		else:
			blue += SR[i]
	ans += memo[red, blue]
print(ans)


from itertools import product
from collections import defaultdict
n = int(input())
s = input()
(sa, sb) = (s[:n], s[n:][::-1])
(a, b, ans) = (defaultdict(int), defaultdict(int), 0)
for p in product(range(2), repeat=n):
	(word_a_1, word_b_1, word_a_2, word_b_2) = ('', '', '', '')
	for j in range(n):
		if p[j]:
			word_a_1 += sa[j]
			word_b_1 += sb[j]
		else:
			word_a_2 += sa[j]
			word_b_2 += sb[j]
	a[word_a_1, word_a_2] += 1
	b[word_b_1, word_b_2] += 1
while a:
	(key, value) = a.popitem()
	ans += value * b[key]
print(ans)


from collections import defaultdict
import sys
N = int(input())
S = input()
Sl = list(S[:N])
Sr = list(reversed(S[N:]))
d_l = defaultdict(int)
d_r = defaultdict(int)
for s in range(1 << N):
	sl1 = ''
	sl2 = ''
	sr1 = ''
	sr2 = ''
	for i in range(N):
		if s & 1 << i:
			sl1 += Sl[i]
			sr1 += Sr[i]
		else:
			sl2 += Sl[i]
			sr2 += Sr[i]
	d_l[sl1 + ' ' + sl2] += 1
	d_r[sr1 + ' ' + sr2] += 1
ans = 0
for (k, v) in d_l.items():
	ans += d_r[k] * v
print(ans)


N = int(input())
S = input()
result = 0
S1 = S[:N]
S2 = S[N:][::-1]

def calc(s, x):
	s1 = ''
	s2 = ''
	for c in s:
		if x & 1:
			s1 += c
		else:
			s2 += c
		x >>= 1
	return (s1, s2)
from collections import defaultdict
kv = defaultdict(int)
for i in range(2 ** N):
	kv[calc(S2, i)] += 1
for i in range(2 ** N):
	result += kv[calc(S1, i)]
print(result)


from itertools import product
from collections import defaultdict
N = int(input())
S = input()
ans = 0
D = defaultdict(int)
for pattern in product([0, 1], repeat=N):
	red = ''.join([s for (s, p) in zip(S[:N], pattern) if p == 0])
	blue = ''.join([s for (s, p) in zip(S[:N], pattern) if p == 1])
	D[red, blue] += 1
for pattern in product([0, 1], repeat=N):
	red = ''.join([s for (s, p) in zip(S[N:], pattern) if p == 0])
	blue = ''.join([s for (s, p) in zip(S[N:], pattern) if p == 1])
	ans += D[blue[::-1], red[::-1]]
print(ans)


from collections import defaultdict
from itertools import combinations

def get_pair(s, cmb):
	(g, h) = (0, 0)
	for i in range(n):
		if i in cmb:
			g <<= 5
			g += s[i]
		else:
			h <<= 5
			h += s[i]
	return (g, h)

def patterns(k, d, e):
	ret = 0
	f = defaultdict(int)
	for cmb in combinations(range(n), k):
		f[get_pair(d, cmb)] += 1
	for cmb in combinations(range(n), k):
		ret += f[get_pair(e, cmb)]
	return ret

def solve(n, b):
	d = b[:n]
	e = b[2 * n - 1:n - 1:-1]
	ans = 0
	if n % 2 == 0:
		for k in range(n // 2):
			ans += 2 * patterns(k, d, e)
		ans += patterns(n // 2, d, e)
	else:
		for k in range(n // 2 + 1):
			ans += 2 * patterns(k, d, e)
	return ans
n = int(input())
s = input()
a = ord('a') - 1
b = [ord(c) - a for c in s]
print(solve(n, b))


import itertools
n = int(input())
s = input()
left = s[:n]
right = s[n:][::-1]
dicleft = {}
for v in itertools.product([0, 1], repeat=n):
	(red, blue) = ('', '')
	for i in range(n):
		if v[i] == 0:
			red += left[i]
		else:
			blue += left[i]
	idx = red + '_' + blue
	if idx in dicleft:
		dicleft[idx] += 1
	else:
		dicleft[idx] = 1
dicright = {}
for v in itertools.product([0, 1], repeat=n):
	(red, blue) = ('', '')
	for i in range(n):
		if v[i] == 0:
			red += right[i]
		else:
			blue += right[i]
	idx = red + '_' + blue
	if idx in dicright:
		dicright[idx] += 1
	else:
		dicright[idx] = 1
ans = 0
for (key, value) in dicleft.items():
	if key in dicright:
		ans += value * dicright[key]
print(ans)


from collections import Counter
from itertools import product
n = int(input())
s = list(input())
s_l = list(reversed(s[n:]))
red = Counter([''.join([s[i] for i in range(n) if bit[i] == 1] + ['|'] + [s[i] for i in range(n) if bit[i] == 0]) for bit in product(range(2), repeat=n)])
blue = Counter([''.join([s_l[i] for i in range(n) if bit[i] == 1] + ['|'] + [s_l[i] for i in range(n) if bit[i] == 0]) for bit in product(range(2), repeat=n)])
ans = 0
for (key, value) in red.items():
	ans += value * blue[key]
print(ans)


from collections import defaultdict
N = int(input())
S = input()
S1 = S[:N]
S2 = S[N:][::-1]
bit = 1 << N
firstList = []
secondList = defaultdict(int)
for i in range(bit):
	blue = ''
	red = ''
	blue2 = ''
	red2 = ''
	for j in range(N):
		if (i >> j) % 2:
			blue += S1[j]
			blue2 += S2[j]
		else:
			red += S1[j]
			red2 += S2[j]
	firstList.append(blue + '-' + red)
	secondList[blue2 + '-' + red2] += 1
ans = 0
for s in firstList:
	ans += secondList[s]
print(ans)


from collections import *
N = int(input())
s = list(input())
cnt = defaultdict(lambda : defaultdict(int))
for S in range(2 ** N):
	(red, blue) = ([], [])
	for i in range(N):
		if S >> i & 1:
			red.append(s[i])
		else:
			blue.append(s[i])
	cnt[''.join(red)][''.join(blue)] += 1
s.reverse()
ans = 0
for S in range(2 ** N):
	(red, blue) = ([], [])
	for i in range(N):
		if S >> i & 1:
			red.append(s[i])
		else:
			blue.append(s[i])
	ans += cnt[''.join(blue)][''.join(red)]
print(ans)