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:
N = int(input())
S = input()

memo = {}
def dp(s1, s2, l1, l2, r1, r2, i):
  #print(i, s1 + '|' +s2)
  if s1 + s2 in memo:
    return memo[s1 + s2]
  if i == 2 * N:
    ret = int(s1 == s2)
  else:
    ret = 0
    if i % 2 == 0:
      c = S[i // 2]
      # S1のl1か、S2のr2に入れる
      if s1[l1] == ' ' and (s2[l1] == ' ' or s2[l1] == c):
        ret += dp(s1[:l1] + c + s1[l1+1:], s2, l1+1, l2, r1, r2, i+1)
      if s2[r2] == ' ' and (s1[r2] == ' ' or s1[r2] == c):
        ret += dp(s1, s2[:r2] + c + s2[r2+1:], l1, l2, r1, r2-1, i+1)
    else:
      c = S[-(i // 2 + 1)]
      # S2のl2か、S1のr1に入れる
      if s1[r1] == ' ' and (s2[r1] == ' ' or s2[r1] == c):
        ret += dp(s1[:r1] + c + s1[r1+1:], s2, l1, l2, r1-1, r2, i+1)
      if s2[l2] == ' ' and (s1[l2] == ' ' or s1[l2] == c):
        ret += dp(s1, s2[:l2] + c + s2[l2+1:], l1, l2+1, r1, r2, i+1)
  memo[s1 + s2] = ret
  return ret


a = S[0] + (' ' * (N-1))
b = ' ' * N

print(dp(a, b, 1, 0, N-1, N-1, 1) * 2)