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 collections import deque

def count(s, t1, t2):
    n = len(s)
    k1 = len(t1)
    k2 = len(t2)
    dp = [[0]*(k1+1) for i in range(n+1)]
    dp[0][0] = 1
    for i in range(n):
        for j in range(k1+1):
            # 次にt1を見るときは t1[j] を見る
            # 次にt2を見るときは t2[i-j]を見る
            if j+1 < k1+1 and t1[j] == s[i]:
                dp[i+1][j+1] += dp[i][j]
            if 0 <= i-j and i-j < k2 and  t2[i-j] == s[i]:
                dp[i+1][j] += dp[i][j]
    return dp[n][k1]

n = int(input())
s = input()
ss = s[n:]

m = 1 << n
ans = 0

for bit_state in range(m):
    red = []
    blue = []
    for i in range(n):
        if 1 << i & bit_state:
            red.append(s[i])
        else:
            blue.append(s[i])

    red = red[::-1]
    blue = blue[::-1]
    ans += count(ss, red, blue)
print(ans)