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: #include <map>
  #include <set>
  #include <list>
  #include <cmath>
  #include <queue>
  #include <stack>
  #include <cstdio>
  #include <string>
  #include <vector>
  #include <complex>
  #include <cstdlib>
  #include <cstring>
  #include <numeric>
  #include <sstream>
  #include <iostream>
  #include <algorithm>
  #include <functional>
    
  #define mp       make_pair
  #define pb       push_back
  #define all(x)   (x).begin(),(x).end()
  #define rep(i,n) for(int i=0;i<(n);i++)
    
  using namespace std;
    
  typedef    long long          ll;
  typedef    unsigned long long ull;
  typedef    vector<bool>       vb;
  typedef    vector<int>        vi;
  typedef    vector<vb>         vvb;
  typedef    vector<vi>         vvi;
  typedef    pair<int,int>      pii;
    
  const int INF=1<<29;
  const double EPS=1e-9;
    
  const int dx[]={1,0,-1,0,1,1,-1,-1},dy[]={0,-1,0,1,1,-1,-1,1};
  
  int dp[50][50];
  
  ll comb(ll n, ll r) {
    if (dp[n][r]) return dp[n][r];
    if (n == r) return dp[n][r] = 1;
    if (r == 0) return dp[n][r] = n;
    return dp[n][r] = comb(n - 1, r - 1) + comb(n - 1, r); 
  }
  
  int main() {
    int N;
    cin >> N;
    string S;
    cin >> S;
    string s1 = S.substr(0, N);
    string s2 = S.substr(N);
    map<pair<string,string>, ll> cnt;
    for(int i = 0; i < 1 << N; i++) {
      string red = "";
      string blue = "";
      for(int j = 0; j < N; j++) {
        if (i >> j & 1) {
          red += s2[j];
        } else {
          blue += s2[j];
        }
      }
      string red_rev = red, blue_rev = blue;
      reverse(red_rev.begin(), red_rev.end());
      reverse(blue_rev.begin(), blue_rev.end());
  
      cnt[mp(red_rev, blue_rev)]++;
    }
  
    ll ans = 0;
    for (int i = 0; i < 1 << N; i++) {
      string red = "";
      string blue = "";
      for(int j = 0; j < N; j++) {
        if (i >> j & 1) {
          red += s1[j];
        } else {
          blue += s1[j];
        }
      }
      ans += cnt[mp(red, blue)];
    }
    cout << ans << endl;
    return 0;
  }
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."}]