Problem:
 Score : 600 points    Problem Statement 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.        Sample Input 1 4
cabaacba      Sample Output 1 4  There are four ways to paint the string, as follows:   c a b a a c b a  c a b a a c b a  c a b a a c b a  c a b a a c b a        Sample Input 2 11
mippiisssisssiipsspiim      Sample Output 2 504       Sample Input 3 4
abcdefgh      Sample Output 3 0       Sample Input 4 18
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa      Sample Output 4 9075135300  The answer may not be representable as a 32 -bit integer.

Solution (Python):
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)

Solution (Python):
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)

if __name__ == '__main__':
    main()

Solution (Python):
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)

Solution (Python):
from itertools import combinations
from collections import defaultdict

n = int(input())
s = str(input())

d = defaultdict(int)
left = set()

for r in range(n + 1):
	for j in combinations(range(n), r):
		sl = ""
		sr = ""
		for i in range(n):
			if i in j:
				sl += s[i]
			else:
				sr += s[i]
		left.add(sl + "," + sr)
		d[sl + "," + sr] += 1
res = 0
for r in range(n + 1):
	for j in combinations(range(n, 2 * n), r):
		sl = ""
		sr = ""
		for i in range(n, 2 * n):
			if i in j:
				sl = s[i] + sl
			else:
				sr = s[i] + sr
		if sr + "," + sl in left:
			res += d[sr + "," + sl]
print(res)

Solution (Python):
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))



from itertools import product

N = I()
S = str(input())


d = defaultdict(lambda:defaultdict(int))
A = list(product([0,1],repeat=N))
for a in A:
    x = []
    y = []
    for i in range(N):
        if a[i]:
            x.append(S[N+i])
        else:
            y.append(S[N+i])
    x = ''.join(x)
    y = ''.join(y)
    d[x][y] += 1



ans = 0
for a in A:
    x = []
    y = []
    for i in range(N):
        if a[i]:
            x.append(S[i])
        else:
            y.append(S[i])
    x = ''.join(x[::-1])
    y = ''.join(y[::-1])
    ans += d[x][y]
    
print(ans)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):

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)


if __name__ == "__main__":
    main()

Solution (Python):
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)

Solution (Python):
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)

if __name__ == '__main__':
	main()

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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+"

  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+"

  print(ans)
  
if __name__ == "__main__":
  main()

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):

ans = 0


def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**6)
    

    n = int(input())
    s = input()[:-1]
    sLatter = s[n:][::-1]

    d = dict()

    def dfs1(i, sR, sB):
        if i == n:
            if not (sR, sB[::-1]) in d:
                d[(sR, sB[::-1])] = 0
            d[(sR, sB[::-1])] += 1
            return
        dfs1(i + 1, sR + s[i], sB)
        dfs1(i + 1, sR, sB + s[i])

    dfs1(0, '', '')
    

    def dfs2(i, sR, sB):
        if i == n:
            if (sR, sB[::-1]) in d:
                global ans
                ans += d[(sR, sB[::-1])]
            return
        dfs2(i + 1, sR + sLatter[i], sB)
        dfs2(i + 1, sR, sB + sLatter[i])

    dfs2(0, '', '')
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from itertools import combinations as combi
from collections import defaultdict as dd
input = sys.stdin.readline
N = int(input())
S = list(input())[: -1]
d = dd(int)
res = 0
for r in range(N + 1):
  for c in combi([x for x in range(N)], r):
    x = []
    y = []
    for i in range(N):
      if i in c: x.append(S[i])
      else: y.append(S[i])
    d["".join(x) + "?" + "".join(y)] += 1

for b in range(N + 1):
  for c in combi([x + N for x in range(N)], b):
    x = []
    y = []
    for i in range(N, N * 2):
      if i in c: x.append(S[i])
      else: y.append(S[i])
    x = x[: : -1]
    y = y[: : -1]
    res += d["".join(x) + "?" + "".join(y)]
print(res)

Solution (Python):
import sys
from itertools import combinations as combi
from collections import defaultdict as dd
input = sys.stdin.readline
N = int(input())
S = list(input())[: -1]
res = 0
s = S[: N]
t = S[N: ]
a = dd(int)
b = dd(int)
for i in range(N + 1):
  for c in combi([x for x in range(N)], i):
    u = []
    v = []
    for j in range(N):
      if j in c: u.append(s[j])
      else: v.append(s[j])
    a["".join(u) + "?" + "".join(v)] += 1

for i in range(N + 1):
  for c in combi([x for x in range(N)], i):
    u = []
    v = []
    for j in range(N):
      if j in c: u.append(t[j])
      else: v.append(t[j])
    b["".join(u) + "?" + "".join(v)] += 1
for ak in a.keys():
  bk = ak[: : -1]
  res += a[ak] * b[bk]
print(res)

Solution (Python):
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)

Solution (Python):
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)


if __name__ == '__main__':
    main()

Solution (Python):
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)


if __name__ == '__main__':
    solve()

Solution (Python):
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

if __name__ == '__main__':
    examC()

Solution (Python):
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

if __name__ == '__main__':
    examC()

Solution (Python):
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)

Solution (Python):
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))


if __name__ == '__main__':
    main()

Solution (Python):
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()

Solution (Python):
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()

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):


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)

Solution (Python):


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 = list(S[:N])

S2 = list(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[(''.join(s1_1), ''.join(s1_2))] += 1
    d2[(''.join(s2_1), ''.join(s2_2))] += 1

ans = 0
for k, v in d1.items():
    
    ans += v * d2[k]
print(ans)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):

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
    k = 27
    m = 1<<n
    p = [1<<j for j in range(n)]
    d = defaultdict(lambda : 0)
    l = [(0,0)]
    for i in s[:n][::-1]:
        l = [(x[0]*k+i, x[1]) for x in l]+[(x[0], x[1]*k+i) for x in l]
    for i in l:
        d[i] += 1
    ans = 0
    l = [(0,0)]
    for i in s[n:]:
        l = [(x[0]*k+i, x[1]) for x in l]+[(x[0], x[1]*k+i) for x in l]
    for i in l:
        ans += d[i]
    print(ans)
    return


def D():

    return


def E():

    return


def F():

    return


if __name__ == "__main__":
    C()

Solution (Python):

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
    k = 27
    m = 1<<n
    p = [1<<j for j in range(n)]
    d = defaultdict(lambda : 0)
    l = [(0,0)]
    for i in s[:n][::-1]:
        l = [(x[0]*k+i, x[1]) for x in l]+[(x[0], x[1]*k+i) for x in l]
    for i in l:
        d[i] += 1
    ans = 0
    l = [(0,0)]
    for i in s[n:]:
        l = [(x[0]*k+i, x[1]) for x in l]+[(x[0], x[1]*k+i) for x in l]
    for i in l:
        ans += d[i]
    print(ans)
    return


def D():

    return


def E():

    return


def F():

    return


if __name__ == "__main__":
    C()