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 = input()
  S_l = S[:N]
  S_r = S[N:][::-1]
  dict_l = {}
  dict_r = {}
  ans = 0
  for num in range(2**N):
      tmpl_1 = ""
      tmpl_2 = ""
      tmpr_1 = ""
      tmpr_2 = ""
      for n in range(N):
          if num >> (N - 1 - n) & 1:
              tmpl_1 += S_l[n]
              tmpr_1 += S_r[n]
          else:
              tmpl_2 += S_l[n]
              tmpr_2 += S_r[n]
      dict_l[[tmpl_1, tmpl_2]] = dict_l.get([tmpl_1, tmpl_2], 0) + 1
      dict_r[[tmpr_1, tmpr_2]] = dict_r.get([tmpr_1, tmpr_2], 0) + 1
  for k, v in dict_l.items():
      ans += v * dict_r.get(k, 0)
  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."}]