output_description: Print the number of ways to paint the string that satisfy the condition.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N
      S
attempt: N = int(input())
  S = list(input())
  
  
  def find(A, B, lst):
      q = (B, A)
      l, r = 0, len(lst)
      while r - l > 1:
          nxt = (l + r) // 2
          print(l, r, nxt, lst[nxt], q)
          if lst[nxt] < q:
              l = nxt
          else:
              r = nxt
      print(lst[l], q)
      if lst[l] >= q:
          return l
      else:
          return r
  
  
  MAX = 2**N
  ans = 0
  first = [S[i] for i in range(N)]
  last = [S[i] for i in range(N, 2 * N)]
  
  search = []
  lasts = [[] for i in range(N + 1)]
  
  for i in range(MAX):
      paint = [False for i in range(N)]
      n = i
      c = 0
      while n > 0:
          paint[c] = n % 2 == 1
          c += 1
          n = n // 2
      A = "".join([first[i] for i in range(N) if paint[i]])
      B = "".join([first[N - i] for i in range(1, N + 1) if not paint[N - i]])
      search.append((A, B))
  
      cnt = sum([1 if p else 0 for p in paint])
      A = "".join([last[i] for i in range(N) if paint[i]])
      B = "".join([last[N - i] for i in range(1, N + 1) if not paint[N - i]])
      lasts[cnt].append((A, B))
  
  for i in range(N):
      lasts[i].sort()
  
  for A, B in search:
      len_B = len(B)
      if len_B > 0 and len_B < N:
          a = list(A)
          a[len(a) - 1] = chr(ord(a[len(a) - 1]) + 1)
          A2 = "".join(a)
          i1 = find(A, B, lasts[len_B])
          i2 = find(A2, B, lasts[len_B])
          print(B, A, A2, lasts[len_B], i2, i1)
          ans += i2 - i1
      elif (B, A) == lasts[len_B][0]:
          ans += 1
  print(ans)
  
problem_description: Statement
  
  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**.
samples: [{"input": "4\n    cabaacba", "output": "4\n    \n\nThere are four ways to paint the string, as follows:\n\n  * cabaacba\n  * cabaacba\n  * cabaacba\n  * cabaacba\n\n* * *"}, {"input": "11\n    mippiisssisssiipsspiim", "output": "504\n    \n\n* * *"}, {"input": "4\n    abcdefgh", "output": "0\n    \n\n* * *"}, {"input": "18\n    aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa", "output": "9075135300\n    \n\nThe answer may not be representable as a 32-bit integer."}]