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

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

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

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

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

Solution (Python):
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] * powb1[cntr]
                hr2 += x[j] * powb2[cntr]
                hr1 %= mod
                hr2 %= mod
                cntr += 1
            else:
                hb1 += x[j] * powb1[cntb]
                hb2 += x[j] * powb2[cntb]
                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)

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

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

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


if __name__ == '__main__':
    N = int(input())
    S = input()
    print(solve(S))

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

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

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

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

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

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

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

Solution (Python):
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[::-1][:N]
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 (b1,r1),v1 in ctr1.items():
    ans += v1 * ctr2[(r1,b1)]
print(ans)

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

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

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

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

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

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




def main():
	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)

if __name__ == '__main__':
	main()

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




def main():
	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)

if __name__ == '__main__':
	main()

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



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:
		ans += dic_f[key] * dic_l[key]

	print(ans)


if __name__ == '__main__':
	main()

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

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:
	ans += dic_f[key] * dic_l[key]

print(ans)

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



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:
		ans += dic_f[key] * dic_l[key]

	print(ans)


if __name__ == '__main__':
	main()

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

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:
	ans += dic_f[key] * dic_l[key]

print(ans)

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

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