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,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007


def A():

    return

def B():

    return


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


def D():

    return


def E():

    return


def F():

    return


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()
    d = defaultdict(lambda : 0)
    alp = list("abcdefghijklmnopqrstuvwxyz")
    f = {}
    for i in range(26):
        f[alp[i]] = i+1
    for i in range(2*n):
        s[i] = f[s[i]]
    for i in range(n>>1):
        s[i],s[n-i-1] = s[n-i-1],s[i]
    k = 27
    m = 1<<n
    p = [1<<j for j in range(n)]
    for i in range(m):
        r = 0
        b = 0
        for j in range(n):
            if i&p[j]:
                r *= k
                r += s[j]
            else:
                b *= k
                b += s[j]
        d[(r,b)] += 1
    ans = 0
    for i in range(m):
        r = 0
        b = 0
        for j in range(n):
            if i&p[j]:
                r *= k
                r += s[j+n]
            else:
                b *= k
                b += s[j+n]
        ans += d[(r,b)]
    print(ans)
    return


def D():

    return


def E():

    return


def F():

    return


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()
    d = defaultdict(lambda : 0)
    alp = list("abcdefghijklmnopqrstuvwxyz")
    f = {}
    for i in range(26):
        f[alp[i]] = i+1
    for i in range(2*n):
        s[i] = f[s[i]]
    for i in range(n>>1):
        s[i],s[n-i-1] = s[n-i-1],s[i]
    k = 27
    m = 1<<n
    p = [1<<j for j in range(n)]
    for i in range(m):
        r = 0
        b = 0
        for j in range(n):
            if i&p[j]:
                r *= k
                r += s[j]
            else:
                b *= k
                b += s[j]
        d[(r,b)] += 1
    ans = 0
    for i in range(m):
        r = 0
        b = 0
        for j in range(n):
            if i&p[j]:
                r *= k
                r += s[j+n]
            else:
                b *= k
                b += s[j+n]
        ans += d[(r,b)]
    print(ans)
    return


def D():

    return


def E():

    return


def F():

    return


if __name__ == "__main__":
    C()

Solution (Python):
import sys
input = sys.stdin.readline

from collections import Counter

N = int(input())
S = input().rstrip()

left = [('','')]
for s in S[:N]:
    left = [(x[0]+s,x[1]) for x in left] + [(x[0],x[1]+s) for x in left]
left = [x+' '+y for x,y in left]
counter_L = Counter(left)

right = [('','')]
for s in S[N:][::-1]:
    right = [(x[0]+s,x[1]) for x in right] + [(x[0],x[1]+s) for x in right]
right = [x+' '+y for x,y in right]

answer = sum(counter_L[s] for s in right)
print(answer)

Solution (Python):
import sys
input = sys.stdin.readline
from collections import defaultdict

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

  ans = 0
  s = s[::-1]
  for i in range(pow(2, n)):
    rd = ""
    bl = ""
    for b in range(n):
      if (i // pow(2, b)) % 2 == 1:
        bl += s[b]
      else:
        rd += s[b]
    ans += pc[(rd, bl)]

  print(ans)


if __name__ == '__main__':
  main()

Solution (Python):
from collections import defaultdict

N = int(input())
S = input()
first = S[:N]
last = S[::-1][:N]

d = defaultdict(int)
ans = 0

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

for i in range(2**N):
  d[paint(first, i)] += 1
  
for i in range(2**N):
  ans += d[paint(last, i)]
  
print(ans)

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

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

Solution (Python):
from collections import Counter

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

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

ans = 0
for key in rb1.keys():
    ans += rb1[key] * rb2[key]

print(ans)

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

ans = 0
for key in front_cnt.keys():
    ans += front_cnt[key] * back_cnt[key]
print(ans)

Solution (Python):
from collections import Counter

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

left, right = S[:N], S[N:][::-1]
a, b = Counter(), Counter()

for i in range(2 ** N):
    t = u = v = w = ""
    for j in range(N):
        if (i >> j) & 1:
            t += left[j]
            u += right[j]
        else:
            v += left[j]
            w += right[j]
    a[t, v] += 1
    b[u, w] += 1

print(sum(a[t] * b[t] for t in a.keys()))

Solution (Python):
from collections import Counter

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

left, right = S[:N], S[N:][::-1]
a, b = Counter(), Counter()

for i in range(2 ** N):
    t = "".join(left[j] if (i >> j) & 1 else "" for j in range(N))
    u = "".join(right[j] if (i >> j) & 1 else "" for j in range(N))
    v = "".join("" if (i >> j) & 1 else left[j] for j in range(N))
    w = "".join("" if (i >> j) & 1 else right[j] for j in range(N))
    a[t, v] += 1
    b[u, w] += 1

print((sum(a[t] * b[t] for t in a.keys())))

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

Solution (Python):
n = int(input())
s = list(input())
l = s[:n]
r = list(reversed(s[n:]))
hashl = {}
hashr = {}
for i in range(1 << n):
    llr = []
    llb = []
    lrr = []
    lrb = []
    for k in range(n):
        if i & (1 << k):
            llr.append(l[k])
            lrr.append(r[k])
        else:
            llb.append(l[k])
            lrb.append(r[k])
    sl = (''.join(llr), ''.join(llb))
    sr = (''.join(lrr), ''.join(lrb))

    if sl not in hashl: hashl[sl] = 1
    else: hashl[sl] += 1
    if sr not in hashr: hashr[sr] = 1
    else: hashr[sr] += 1
ret = 0
for strpair, c in hashl.items():
    if strpair in hashr:
        ret += hashr[strpair] * c
print(ret)

Solution (Python):
from itertools import product, compress
from collections import Counter

N = int(input())
Ss = input()

S1s = Ss[:N]
ptn1s = [''.join(compress(S1s, sels)) for sels in product(range(2), repeat=N)]
cnt1 = Counter([(red, blue) for red, blue in zip(ptn1s, reversed(ptn1s))])

S2s = Ss[N:][::-1]
ptn2s = [''.join(compress(S2s, sels)) for sels in product(range(2), repeat=N)]
cnt2 = Counter([(red, blue) for red, blue in zip(ptn2s, reversed(ptn2s))])

ans = 0
for ptn1, num1 in cnt1.items():
    ans += num1 * cnt2[ptn1]
print(ans)

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

Solution (Python):
from collections import deque

def comb(s):
    p = deque([('','')])

    for i in range(len(s)):
        for j in range(2**i):
            e = p.pop()
            p.appendleft((e[0]+s[i],e[1]))
            p.appendleft((e[0],e[1]+s[i]))
    return p

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

sl = s[0:n]
sr = s[n:2*n][::-1]
keys1 = [c[0]+'-'+c[1] for c in comb(sl)]
keys2 = [c[0]+'-'+c[1] for c in comb(sr)]

dict = {}
for key1 in keys1:
    if key1 in dict:
        dict[key1] += 1
    else:
        dict[key1] = 1
cnt = 0
for key2 in keys2:
    if key2 in dict:
        cnt += dict[key2]

print(cnt)

Solution (Python):
from collections import defaultdict

n = int(input())
s = input()
s1 = s[:n]
s2 = s[n:][::-1]
def makeDic(s):
    dic = defaultdict(int)
    for i in range(2 ** n):
        mask = 1
        c1 = ""
        c2 = ""
        for j in range(n):
            if i & mask:
                c1 += s[j]
            else:
                c2 += s[j]
            mask <<= 1
        dic[(c1, c2)] += 1
    return dic


dic1 = makeDic(s1)
dic2 = makeDic(s2)
ans = 0
for key in dic1:
    if key in dic2:
        ans += dic1[key] * dic2[key]
print(ans)

Solution (Python):
N = int(input())
S = input()


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


h1 = count(S[:N])
h2 = count(S[N:][::-1])
ans = 0
for k, v in h1.items():
    if k in h2:
        ans += v * h2[k]
print(ans)

Solution (Python):
N = int(input())
S = input()


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


h1 = count(S[:N])
h2 = count(S[N:][::-1])
ans = 0
for k, v in h1.items():
    if k in h2:
        ans += v * h2[k]
print(ans)

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

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

Solution (Python):
N=int(input())
s=input()

sa=s[:N]
sb=s[N:]

import itertools
ALLIST=itertools.product((0,1),repeat=N)

from collections import defaultdict
STRA = defaultdict(int)
STRB = defaultdict(int)

for i in ALLIST:
    red_a=""
    blue_a=""
    red_b=""
    blue_b=""
    for j in range(N):
        if i[j]==0:
            red_a+=sa[j]
            red_b+=sb[j]
        else:
            blue_a+=sa[j]
            blue_b+=sb[j]

    STRA[(red_a[::-1],blue_a[::-1])]+=1
    STRB[(red_b,blue_b)]+=1

ANS=0
for key in STRA:
    ANS+=STRA[key]*STRB[key]

print(ANS)

Solution (Python):
N=int(input())
s=input()

sa=s[:N]
sb=s[N:]

import itertools
ALLIST=list(itertools.product((0,1),repeat=N))

from collections import defaultdict
STRA = defaultdict(int)
STRB = defaultdict(int)

for i in ALLIST:
    red_a=""
    blue_a=""
    red_b=""
    blue_b=""
    for j in range(N):
        if i[j]==0:
            red_a+=sa[j]
            red_b+=sb[j]
        else:
            blue_a+=sa[j]
            blue_b+=sb[j]

    STRA[(red_a[::-1],blue_a[::-1])]+=1
    STRB[(red_b,blue_b)]+=1

ANS=0
for key in STRA:
    ANS+=STRA[key]*STRB[key]

print(ANS)

Solution (Python):
N=int(input())
s=input()

sa=s[:N]
sb=s[N:]

import itertools
ALLIST=list(itertools.product((0,1),repeat=N))

from collections import defaultdict
STRA = defaultdict(int)
STRB = defaultdict(int)

for i in ALLIST:
    red_a=""
    blue_a=""
    red_b=""
    blue_b=""
    for j in range(N):
        if i[j]==0:
            red_a+=sa[j]
            red_b+=sb[j]
        else:
            blue_a+=sa[j]
            blue_b+=sb[j]

    STRA[(red_a[::-1],blue_a[::-1])]+=1
    STRB[(red_b,blue_b)]+=1

ANS=0
for key in STRA:
    ANS+=STRA[key]*STRB[key]

print(ANS)

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

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

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

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

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

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

Solution (Python):
n = int(input())
s = input()

sl = s[:n]
sr = s[n:][::-1]

from collections import Counter
l = Counter()
r = Counter()

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

print(ans)

Solution (Python):
from collections import defaultdict
N=int(input())
S=input()
A=S[:N]
B=S[N:]
B=B[::-1]
def f(A):
    dd=defaultdict(int)
    for i in range(1<<N):
        a=''
        b=''
        for j in range(N):
            if i&(1<<j):
                a+=A[j]
            else:
                b+=A[j]
        dd[(a,b)]+=1
    return dd
dd1=f(A)
dd2=f(B)
ans=0
for t,c in dd1.items():
    ans+=dd2[t]*c
print(ans)

Solution (Python):
from collections import defaultdict
N=int(input())
S=input()
A=S[:N]
B=S[N:]
B=B[::-1]
def f(A):
    dd=defaultdict(int)
    for i in range(1<<N):
        a=''
        b=''
        for j in range(N):
            if i&(1<<j):
                a+=A[j]
            else:
                b+=A[j]
        dd[(a,b)]+=1
    return dd
dd1=f(A)
dd2=f(B)
ans=0
for t,c in dd1.items():
    ans+=dd2[t]*c
print(ans)

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

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

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


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

    return r


print(main())

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


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

    return r


print(main())

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


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


    return r


print(main())

Solution (Python):
from collections import defaultdict

N = int(input())
S = input()
left = S[:N]
right = S[:N-1:-1]


br_pattern = defaultdict(int)

for bit in range(1<<N):
    blue = ""
    red = ""
    for isb in range(N):
        if bit & (1<<isb):
            blue = blue + left[isb]
        else:
            red = red + left[isb]
            
    br_pattern[(blue, red)] += 1


ans = 0
for bit in range(1<<N):
    red = ""
    blue = ""
    for isr in range(N):
        if bit & (1<<isr):
            red = red + right[isr]
        else:
            blue = blue + right[isr]
            
    ans += br_pattern[(red, blue)]
        
print(ans)

Solution (Python):
def run(n, s):
    '''
    文字列sを半分に分けて、右半分を逆順に並び替える
    さらに色の塗分けを逆にすると、左半分と右半分は
    同じになる
    '''
    sl = s[0:n]
    sr = s[n:2*n][::-1]

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


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


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


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


if __name__ == '__main__':
    main()

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

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

Solution (Python):
def run(n, s):
    '''
    文字列sを半分に分けて、右半分を逆順に並び替える
    さらに色の塗分けを逆にすると、左半分と右半分は
    同じになる
    '''
    sl = s[0:n]
    sr = s[n:2*n][::-1]

    dic = {}
    keys = []
    cnt = 0

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

    for key in keys:
        cnt += dic.get(key, 0)
    return cnt

    '''
    keys1 = [c[0]+'-'+c[1] for c in comb(sl)]
    keys2 = [c[0]+'-'+c[1] for c in comb(sr)]
    cnt = 0
    for key1 in keys1:
        cnt += keys2.count(key1)
    return cnt
    '''
    '''
    dict = {}
    for t0, t1 in keys:
        key = t0 + '-' + t1
        cnt = has_key(sr, t0, t1)
        if key in dict:
            dict[key] += cnt
        else:
            dict[key] = cnt
    return sum(dict.values())
    '''


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


'''
def has_key(s, t0, t1):
    cnt = 0
    if len(s) == 1:
        if s == t0:
            return 1
        elif s == t1:
            return 1
        else:
            return 0
    else:
        a = s[0]
        if len(t0) != 0 and a == t0[0]:
            cnt += has_key(s[1:len(s)], t0[1:len(t0)], t1)
        if len(t1) != 0 and a == t1[0]:
            cnt += has_key(s[1:len(s)], t0, t1[1:len(t1)])
    return cnt
'''


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


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


if __name__ == '__main__':
    main()

Solution (Python):

from collections import defaultdict

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

def paint(X, i):
    r = ""
    b = ""
    for j, k in enumerate(format(i, "b").zfill(N)):
        if k == "1":
            r += X[j]
        else:
            b += X[j]
    return r, b

for i in range(2**N):
    r, b = paint(A, i)
    D[(r, b)] += 1

for i in range(2**N):
    r, b = paint(B, i)
    ans += D[(b[::-1], r[::-1])]

print(ans)