Perfect Separating

#include <bits/stdc++.h>

using namespace std;

const int N = 77;
const int G = 30;

int n;
char s[N];

int half;

map<int, int> cnt[N];
long long ans;

int suf(int mask, int i) {
    return mask & ((1 << i) - 1);
}

void goLeft(int i, int sx, int sy, int x, int y) {
    if (i == half) {
        if (sx <= sy) {
            if (x != suf(y, sx)) return;
            ++cnt[sx - sy + G][y >> sx];
        } else {
            if (y != suf(x, sy)) return;
            ++cnt[sx - sy + G][x >> sy];
        }
        return;
    }
    goLeft(i + 1, sx + 1, sy, x | (int(s[i]) << sx), y);
    goLeft(i + 1, sx, sy + 1, x, y | (int(s[i]) << sy));
}

void goRight(int i, int sx, int sy, int x, int y) {
    if (i < half) {
        if (sx <= sy) {
            if (x != (y >> (sy - sx))) return;
            ans += cnt[sy - sx + G][suf(y, sy - sx)];
        } else {
            if (y != (x >> (sx - sy))) return;
            ans += cnt[sy - sx + G][suf(x, sx - sy)];
        }
        return;
    }
    goRight(i - 1, sx + 1, sy, x << 1 | s[i], y);
    goRight(i - 1, sx, sy + 1, x, y << 1 | s[i]);
}

int main() {
    cin >> s;
    n = strlen(s);
    half = n / 2;
    for (int i = 0; i < n; ++i) s[i] -= 'a';

    goLeft(0, 0, 0, 0, 0);
    goRight(n - 1, 0, 0, 0, 0);

    cout << ans << endl;
    return 0;
}