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