CF#537 | Destroy the Colony

https://codeforces.com/contest/1111/problem/D
We first find the generating function of whole elements.
\begin{align}
(1+x^\bigcirc)(1+x^\bigcirc) \cdots (1+x^\bigcirc)
\end{align}
Dividing $(1+x^\bigcirc)^{-1}$, we obtain the answer.
#include <stdio.h>
#include <string.h>

#define MOD 1000000007

struct mint {
    int n;
    mint(int n_ = 0) : n(n_) {}
};

mint operator+(mint a, mint b) { a.n += b.n; if (a.n >= MOD) a.n -= MOD; return a; }
mint operator-(mint a, mint b) { a.n -= b.n; if (a.n < 0) a.n += MOD; return a; }
mint operator*(mint a, mint b) { return (long long)a.n * b.n % MOD; }
mint &operator+=(mint &a, mint b) { return a = a + b; }
mint &operator-=(mint &a, mint b) { return a = a - b; }
mint &operator*=(mint &a, mint b) { return a = a * b; }

mint F[100001] = {1, 1};
mint IF[100001] = {1, 1};
mint I[100001] = {0, 1};

mint dp[53][50001];
int N;
char S[100001];
int A[52];
int A_[52];

int min(int x, int y) {
    return x < y ? x : y;
}

int f(int c) {
    if ('a' <= c && c <= 'z') {
        return c - 'a';
    } else {
        return c - 'A' + 26;
    }
}

void susume(int i) {
    if (A[i] == 0) {
        for (int j = 0; j <= N / 2; j++) {
            dp[i + 1][j] = dp[i][j];
        }
    } else {
        for (int j = 0; j <= N / 2; j++) {
            if (j >= A[i]) {
                dp[i + 1][j] = dp[i][j] + dp[i][j - A[i]];
            } else {
                dp[i + 1][j] = dp[i][j];
            }
        }
    }
}

void modore(int i) {
    for (int j = 0; j <= N / 2; j++) {
        if (j >= A[i]) {
            dp[i][j] = dp[i + 1][j] - dp[i][j - A[i]];
        } else {
            dp[i][j] = dp[i + 1][j];
        }
    }
}

int main() {
    for (int i = 2; i <= 100000; i++) {
        I[i] = I[MOD % i] * (MOD - MOD / i);
        F[i] = i * F[i - 1];
        IF[i] = I[i] * IF[i - 1];
    }
    scanf("%s", S);
    N = strlen(S);
    for (int i = 0; i < N; i++) {
        A[f(S[i])]++;
    }
    dp[0][0] = 1;
    for (int i = 0; i < 52; i++) {
        susume(i);
    }
    for (int i = 0; i < 52; i++) {
        A_[i] = A[i];
    }
    static mint ans[52][52];
    for (int x = 0; x < 52; x++) {
        if (A_[x] == 0) continue;
        ans[x][x] = dp[52][N / 2];
        A[51] = A_[x];
        modore(51);
        for (int y = x + 1; y < 52; y++) {
            if (A_[y] == 0) continue;
            A[50] = A_[y];
            modore(50);
            int s = A_[x] + A_[y];
            if (s > N / 2) {
                ans[x][y] = ans[y][x] = 0;
            } else {
                ans[x][y] = ans[y][x] = dp[50][N / 2] + dp[50][N / 2 - s];
            }
        }
    }
    mint v = F[N / 2] * F[N / 2];
    for (int i = 0; i < 52; i++) {
        v *= IF[A_[i]];
    }
    int q;
    scanf("%d", &q);
    while (q--) {
        int x, y;
        scanf("%d %d", &x, &y);
        x--; y--;
        x = f(S[x]);
        y = f(S[y]);
        printf("%d\n", (v * ans[x][y]).n);
    }
    return 0;
}