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 CPP):

Solution:
#include <bits/stdc++.h>
#define int long long
using namespace std;

int N;
string s;

typedef pair<string,string> P;

map<P,int> A[2];

void cal(string s, int idx){
  
  for(int i=0;i<(1<<N);i++){
    
    string a, b;
    
    for(int j=0;j<N;j++){
      if( ( i >> j ) & 1 ) a += s[j];
      else b += s[j];
    }
    
    reverse( b.begin(), b.end() );
    
    A[idx][P(a+b,b)]++;
    
  }
  
}

void solve(){
  
  cal( s.substr( 0, N ), 0 );
  
  string tmp = s.substr( N, N );
  reverse(tmp.begin(), tmp.end());
  
  cal( tmp, 1 );
  
  int ans = 0;
  
  for(pair<P,int> p : A[0] ) ans += p.second * A[1][p.first];
  
  cout<<ans<<endl;
  
}

signed main(){
  
  cin>>N>>s;
  
  solve();
  
  return 0;
}