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
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)

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


if __name__ == '__main__':
    main()

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

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

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

Solution (Python):
'''
自宅用PCでの解答
'''
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

if __name__ == '__main__':
    main()

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

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

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

Solution (Python):
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)
if __name__ == "__main__":
    f()

Solution (Python):
def f():
    n,s=int(input()),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:
        ans+=bd[k]*ad[k]
    print(ans)
if __name__ == "__main__":
    f()

Solution (Python):
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)
if __name__ == "__main__":
    t()

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

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

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

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

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

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

Solution (Python):
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)
if __name__ == "__main__":
    f()

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

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

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

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

Solution (Python):


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)

Solution (Python):

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)
    if key in dic_left:
        dic_left[key] += 1
    else:
        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)
    if key in dic_right:
        dic_right[key] += 1
    else:
        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)

Solution (Python):

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)

Solution (Python):

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
former = S[:N]
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)
    if key in dic_left:
        dic_left[key] += 1
    else:
        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)
    if key in dic_right:
        dic_right[key] += 1
    else:
        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)

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

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

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


if __name__ == '__main__':
    solve()

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


if __name__ == '__main__':
	main()

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

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

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

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

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

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

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

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

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

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.append(string[c])
    else:
      t.append(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

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)

if __name__ == "__main__":
    main()

Solution (Python):

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)

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