orz qyc
设 \(m=\frac{|s|}{2}\)．
看起来很像背包，由基础组合数学知识可知，把每个字符出现次数看做体积为 \(1\) 的物品，做 01 背包后 \(m\) 能被凑出的方案数，乘上 \((m!)^2\) 再除去每个数出现次数的阶乘即为没有限制的答案。
有限制了怎么做？可以看成删去这两个物品，然后把两个物品捆绑在一起加进来，做 01 背包。这个题就变成了 LuoguP4141 消失之物。
注意到字符集大小为 \(52\)，所以本质不同的询问仅有 \(52^2\) 个。
由于背包放进去物品的顺序没有关系，所以删去一个物品的时候直接顺序一遍减掉贡献即可。
设字符集大小为 \(|E|\)，则复杂度为 \(\mathcal{O}(|E|^2n+q)\)．
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
typedef long long ll;
const ll mod = 1000000007;
template <typename T> T Add(T x, T y) { return (x + y >= mod) ? (x + y - mod) : (x + y); }
template <typename T> T cAdd(T x, T y) { return x = (x + y >= mod) ? (x + y - mod) : (x + y); }
template <typename T> T Mul(T x, T y) { return x * y % mod; }
template <typename T> T Mod(T x) { return x < 0 ? (x + mod) : x; }
template <typename T> T Max(T x, T y) { return x > y ? x : y; }
template <typename T> T Min(T x, T y) { return x < y ? x : y; }
template <typename T> T Abs(T x) { return x < 0 ? -x : x; }
template <typename T> T chkmax(T &x, T y) { return x = x > y ? x : y; }
template <typename T>
T &read(T &r) {
r = 0; bool w = 0; char ch = getchar();
while(ch < '0' || ch > '9') w = ch == '-' ? 1 : 0, ch = getchar();
while(ch >= '0' && ch <= '9') r = (r << 3) + (r <<1) + (ch ^ 48), ch = getchar();
return r = w ? -r : r;
}
ll qpow(ll x, ll y) {
ll sumq = 1;
while(y) {
if(y & 1) sumq = sumq * x % mod;
x = x * x % mod;
y >>= 1;
}
return sumq;
}
const int N = 100010;
int n, m, q, a[N], vis[53];
ll f[N], ans[53][53];
ll fac[N], inv[N];
char ch[N];
int char_to_int(char x) {
if(x >= 'a' && x <= 'z') return x-'a';
return x-'A'+26;
}
void add(int s) {
if(!s) return ;
for(int i = m; i >= s; --i) f[i] = Add(f[i], f[i-s]);
}
void del(int s) {
if(!s) return ;
for(int i = s; i <= m; ++i) f[i] = Add(f[i], Mod(-f[i-s]));
}
signed main() { //freopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);
scanf("%s", ch+1); n = std::strlen(ch+1); m = n / 2;
for(int i = 1; i <= n; ++i) a[i] = char_to_int(ch[i]);
fac[0] = 1; for(int i = 1; i <= n; ++i) fac[i] = fac[i-1] * i % mod;
inv[n] = qpow(fac[n], mod-2);
for(int i = n-1; ~i; --i) inv[i] = inv[i+1] * (i+1) % mod;
for(int i = 1; i <= n; ++i) ++vis[a[i]];
f[0] = 1;
ll mul = fac[m] * fac[m] % mod;
for(int i = 0; i < 52; ++i) {
add(vis[i]);
mul = mul * inv[vis[i]] % mod;
}
for(int i = 0; i < 52; ++i) ans[i][i] = f[m];
for(int i = 0; i < 52; ++i)
for(int j = i+1; j < 52; ++j) {
del(vis[i]); del(vis[j]);
add(vis[i]+vis[j]);
ans[i][j] = ans[j][i] = f[m];
del(vis[i]+vis[j]);
add(vis[i]); add(vis[j]);
}
read(q);
for(int i = 1; i <= q; ++i) {
int x, y; read(x); read(y);
printf("%lld\n", ans[a[x]][a[y]] * mul % mod);
}
return 0;
}