#include <bits/stdc++.h>
using namespace std;

map <pair <string, string>, int> mp;
long long ans;

void solve(string s, bool add)
{
    for (int mask = 0; mask < (1 << s.size()); mask++) {
        string a, b;
        for (int i = 0; i < s.size(); i++) {
            if (mask & (1 << i))
                a.push_back(s[i]);
            else
                b.push_back(s[i]);
        }

        if (add)
            mp[{ a, b }]++;
        else
            ans += mp[{ a, b }];
    }
}

int main()
{
    int n;
    cin >> n;
    string s;
    cin >> s;

    string s1 = s.substr(0, n), s2 = s.substr(n, n);

    reverse(s2.begin(), s2.end());

    solve(s1, 1);
    solve(s2, 0);

    cout << ans << '\n';
    return 0;
}

### Prompt

Please provide a Cpp coded solution 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;

map <pair <string, string>, int> mp;
long long ans;

void solve(string s, bool add)
{
    for (int mask = 0; mask < (1 << s.size()); mask++) {
        string a, b;
        for (int i = 0; i < s.size(); i++) {
            if (mask & (1 << i))
                a.push_back(s[i]);
            else
                b.push_back(s[i]);
        }

        if (add)
            mp[{ a, b }]++;
        else
            ans += mp[{ a, b }];
    }
}

int main()
{
    int n;
    cin >> n;
    string s;
    cin >> s;

    string s1 = s.substr(0, n), s2 = s.substr(n, n);

    reverse(s2.begin(), s2.end());

    solve(s1, 1);
    solve(s2, 0);

    cout << ans << '\n';
    return 0;
}

```