#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
map< pair<string,string> , ll >mp[2];
void solve(string s,ll idx,string r,string b,ll t){
    if(idx==s.size()){
        if(t==0)mp[t][{r,b}]++;
        else mp[t][{b,r}]++;
        return;
    }
    solve(s,idx+1,r+s[idx],b,t);
    solve(s,idx+1,r,b+s[idx],t);
}
int main(){
    ios_base:: sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    ll n;cin>>n;
    string s;cin>>s;
    solve(s.substr(0,n),0,"","",0);

    s = s.substr(n);
    reverse(s.begin(),s.end());
    solve(s,0,"","",1);

    ll ans = 0;
    for(auto &ele:mp[0])ans+=ele.second*mp[1][ele.first];
    cout<<ans;
}



### Prompt

Create a solution in Cpp for the following 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

### Response

```cpp
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
map< pair<string,string> , ll >mp[2];
void solve(string s,ll idx,string r,string b,ll t){
    if(idx==s.size()){
        if(t==0)mp[t][{r,b}]++;
        else mp[t][{b,r}]++;
        return;
    }
    solve(s,idx+1,r+s[idx],b,t);
    solve(s,idx+1,r,b+s[idx],t);
}
int main(){
    ios_base:: sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    ll n;cin>>n;
    string s;cin>>s;
    solve(s.substr(0,n),0,"","",0);

    s = s.substr(n);
    reverse(s.begin(),s.end());
    solve(s,0,"","",1);

    ll ans = 0;
    for(auto &ele:mp[0])ans+=ele.second*mp[1][ele.first];
    cout<<ans;
}



```