#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define sp pair<string,string>

int N;
string S;
map<sp,int> mp;

void dfs1(string r, string b, int idx){
    if(idx == N){
        mp[{r, b}]++;
    }else{
        dfs1(r + S[idx], b, idx + 1);
        dfs1(r, b + S[idx], idx + 1);
    }
}

ll dfs2(string r, string b, int idx){
    if(idx == N - 1){
        return mp[{b,r}];
    }else{
        return dfs2(r + S[idx], b, idx - 1) + dfs2(r, b + S[idx], idx - 1);
    }
}

int main(){
    cin >> N >> S;

    dfs1("", "", 0);
    cout << dfs2("", "", 2 * N - 1) << endl;
    return 0;
}
### Prompt

Develop a solution in Cpp to the problem described below:

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>
using namespace std;
#define ll long long
#define sp pair<string,string>

int N;
string S;
map<sp,int> mp;

void dfs1(string r, string b, int idx){
    if(idx == N){
        mp[{r, b}]++;
    }else{
        dfs1(r + S[idx], b, idx + 1);
        dfs1(r, b + S[idx], idx + 1);
    }
}

ll dfs2(string r, string b, int idx){
    if(idx == N - 1){
        return mp[{b,r}];
    }else{
        return dfs2(r + S[idx], b, idx - 1) + dfs2(r, b + S[idx], idx - 1);
    }
}

int main(){
    cin >> N >> S;

    dfs1("", "", 0);
    cout << dfs2("", "", 2 * N - 1) << endl;
    return 0;
}
```