#include<bits/stdc++.h>
#define maxn 50

using namespace std;
typedef long long ll;
char s[maxn],f[maxn],g[maxn];
int n,m,p,q;
ll dp[20][20],ans;

int main(){
    cin >> n;
    scanf("%s",s);
    for (int i=0;i<(1<<n);i++){
        p=0; q=0;
        for (int j=0;j<n;j++) if (i&(1<<j)) f[p++]=s[j]; else g[q++]=s[j];
        memset(dp,0,sizeof(dp)); dp[0][0]=1;
        for (int j=0;j<n;j++) for (int k=0;k<=j;k++) if (dp[k][j-k]){
            dp[k+1][j-k]+=dp[k][j-k]*(k<p&&s[n*2-j-1]==f[k]);
            dp[k][j-k+1]+=dp[k][j-k]*(j-k<q&&s[n*2-j-1]==g[j-k]);
        }
        ans+=dp[p][q];
    }
    cout << ans << endl;
}

### Prompt

Please formulate a Cpp solution to 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>
#define maxn 50

using namespace std;
typedef long long ll;
char s[maxn],f[maxn],g[maxn];
int n,m,p,q;
ll dp[20][20],ans;

int main(){
    cin >> n;
    scanf("%s",s);
    for (int i=0;i<(1<<n);i++){
        p=0; q=0;
        for (int j=0;j<n;j++) if (i&(1<<j)) f[p++]=s[j]; else g[q++]=s[j];
        memset(dp,0,sizeof(dp)); dp[0][0]=1;
        for (int j=0;j<n;j++) for (int k=0;k<=j;k++) if (dp[k][j-k]){
            dp[k+1][j-k]+=dp[k][j-k]*(k<p&&s[n*2-j-1]==f[k]);
            dp[k][j-k+1]+=dp[k][j-k]*(j-k<q&&s[n*2-j-1]==g[j-k]);
        }
        ans+=dp[p][q];
    }
    cout << ans << endl;
}

```