题目链接：http://codeforces.com/contest/1111/problem/D
题目大意：
这道题题目意思比较模糊。
给定一个字符串，不同字符代表不同种类的坏人，
现在给定若干个询问，每个询问给两个下标，
要求把给定位置上的两个（或一个)类型的人放到同一边，
并且其他相同种类的人均在同一边的方案数。
题目分析：
首先考虑不加限制的计数方案，
就是说不考虑和种类在同一边的情况。
如果单独考虑一边，把半边的情况选好了那另一半的情况也是类似，
但是半边的计数方案和具体的选择种类有关系，就算我们通过组合公式
来执行背包计数也无法把两边的计数方案结合到一起去，那么不妨两边一块考虑，
分母消去所有种类的重复度，分子是两边长度阶乘的贡献：，
对这部分只要处理常用的阶乘逆元即可。
下面先算总体贡献：.这部分用普通的背包计数即可。
如何把两个询问下标考虑进去需要利用到退背包的知识，即在集合S中不考虑第i种物品的情况下
对目标值所产生的计数，设为,那么有如下递推方程：
对于两个查询下标种类一样的情况其实本质差不多，少退一次背包而已。
时间复杂度：O(52*52*N)。
#include<bits/stdc++.h>
using namespace std;#define debug puts("YES");
#define rep(x,y,z) for(int (x)=(y);(x)<(z);(x)++)
#define ll long long#define lrt int l,int r,int rt
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define root l,r,rt
#define mst(a,b) memset((a),(b),sizeof(a))
#define pii pair<int,int>
#define fi first
#define se second
#define mk(x,y) make_pair(x,y)
const int mod=1e9+7;
const int maxn=1e5+5;
const int ub=1e6;
const double inf=1e-4;
ll powmod(ll x,ll y){ll t; for(t=1;y;y>>=1,x=x*x%mod) if(y&1) t=t*x%mod; return t;}
ll gcd(ll x,ll y){return y?gcd(y,x%y):x;}
/*
题目大意：*/
char s[maxn];
int len,cnt[52],q,x,y;
ll dp[maxn],g[maxn],ans[52][52];
int idx(char c){if(c<='z'&&c>='a') return c-'a';return 26+c-'A';
}
ll fac[maxn],inv[maxn];
void init(){fac[0]=1;rep(i,1,maxn) fac[i]=fac[i-1]*i%mod;inv[maxn-1]=powmod(fac[maxn-1],mod-2);for(int i=maxn-2;i>=0;i--) inv[i]=inv[i+1]*(i+1)%mod;
}
ll C(ll p,ll q){return fac[p]*inv[q]%mod*inv[p-q]%mod;
}
void Back(int x){rep(k,0,x) g[k]=dp[k];rep(k,x,len/2+1) g[k]=(dp[k]-g[k-x]+mod)%mod;
}
int main(){init();scanf("%s",s);len=strlen(s);///rep(i,0,len) cnt[idx(s[i])]++;mst(dp,0),mst(g,0),dp[0]=1;rep(i,0,52) if(cnt[i]) for(int j=len/2;j>=cnt[i];j--)(dp[j]+=dp[j-cnt[i]])%=mod;///背包DP计数mst(ans,0);///rep(i,0,52) rep(j,i,52){Back(cnt[i]);///退背包过程if(i!=j) rep(k,cnt[j],len/2+1)g[k]=(g[k]-g[k-cnt[j]]+mod)%mod;ans[i][j]=g[len/2];}ll xishu=fac[len/2]*fac[len/2]%mod;rep(i,0,52) xishu=xishu*inv[cnt[i]]%mod;cin>>q;rep(i,0,q){cin>>x>>y;x=idx(s[x-1]),y=idx(s[y-1]);ll ret=max(ans[x][y],ans[y][x]);ret=ret*2%mod*xishu%mod;cout<<ret<<endl;}return 0;
}