from itertools import product, compress



N = int(eval(input()))

Ss = eval(input())



Fss = [list(compress(Ss[:N], sels))[::-1] for sels in product([0, 1], repeat=N)]



ans = 0

for iFs in range(2 ** N):

    Fs = Fss[iFs]

    Gs = Fss[2 ** N - 1 - iFs]



    lenF = len(Fs)

    lenG = N - lenF

    dp = [1] + [0] * lenF

    for i, s in enumerate(Ss[N:]):

        dp2 = [0] * (lenF + 1)

        for j in range(lenF + 1):

            if dp[j] == 0: continue

            if j < lenF and s == Fs[j]:

                dp2[j+1] += dp[j]

            if 0 <= i-j < lenG and s == Gs[i-j]:

                dp2[j] += dp[j]

        dp = dp2



    ans += dp[lenF]



print(ans)

from itertools import product, compress

from collections import Counter



N = int(eval(input()))

Ss = eval(input())



S1s = Ss[:N]

ptn1s = [''.join(compress(S1s, sels)) for sels in product(list(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(list(range(2)), repeat=N)]

cnt2 = Counter([(red, blue) for red, blue in zip(ptn2s, reversed(ptn2s))])



ans = 0

for ptn1, num1 in list(cnt1.items()):

    ans += num1 * cnt2[ptn1]

print(ans)

from itertools import product, compress

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

from itertools import product, compress
from collections import Counter

N = int(eval(input()))
Ss = eval(input())
S1s = Ss[:N]
ptn1s = ["".join(compress(S1s, sels)) for sels in product(list(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(list(range(2)), repeat=N)]
cnt2 = Counter([(red, blue) for red, blue in zip(ptn2s, reversed(ptn2s))])
ans = 0
for ptn1, num1 in list(cnt1.items()):
    ans += num1 * cnt2[ptn1]
print(ans)

+from collections import Counter -Fss = [list(compress(Ss[:N], sels))[::-1] for sels in product([0, 1], repeat=N)] +S1s = Ss[:N] +ptn1s = ["".join(compress(S1s, sels)) for sels in product(list(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(list(range(2)), repeat=N)] +cnt2 = Counter([(red, blue) for red, blue in zip(ptn2s, reversed(ptn2s))]) -for iFs in range(2**N): -    Fs = Fss[iFs] -    Gs = Fss[2**N - 1 - iFs] -    lenF = len(Fs) -    lenG = N - lenF -    dp = [1] + [0] * lenF -    for i, s in enumerate(Ss[N:]): -        dp2 = [0] * (lenF + 1) -        for j in range(lenF + 1): -            if dp[j] == 0: -                continue -            if j < lenF and s == Fs[j]: -                dp2[j + 1] += dp[j] -            if 0 <= i - j < lenG and s == Gs[i - j]: -                dp2[j] += dp[j] -        dp = dp2 -    ans += dp[lenF] +for ptn1, num1 in list(cnt1.items()): +    ans += num1 * cnt2[ptn1]