Problem: 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.

Examples

Input

4
cabaacba


Output

4


Input

11
mippiisssisssiipsspiim


Output

504


Input

4
abcdefgh


Output

0


Input

18
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa


Output

9075135300

Solution (in PYTHON3):

Solution:
import itertools
import os
import sys
from collections import defaultdict

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

# 解説AC
N = int(sys.stdin.readline())
S = sys.stdin.readline().rstrip()


def test(N, S):
    import numpy as np
    S = np.array(list(S))
    ret = 0
    for r in itertools.combinations(range(N * 2), r=N):
        r = np.array(np.bincount(r, minlength=N * 2), dtype=bool)
        red = ''.join(S[r])
        blue = ''.join(S[~r])
        ret += red == blue[::-1]
    return ret


# print(test(N, S))

S, T = S[:N], S[:N - 1:-1]

t_counts = defaultdict(int)
for choice in itertools.product([0, 1], repeat=N):
    t = ''
    rev = ''
    for i, c in enumerate(choice):
        t += T[i] if c else ''
        rev += '' if c else T[i]
    t_counts[(t, rev)] += 1

ans = 0
for choice in itertools.product([0, 1], repeat=N):
    s = ''
    rev = ''
    for i, c in enumerate(choice):
        s += S[i] if c else ''
        rev += '' if c else S[i]
    ans += t_counts[(s, rev)]
print(ans)