#include using namespace std; #define fRead(x) freopen(x,"r",stdin) #define fWrite(x) freopen (x,"w",stdout) #define LL long long #define ULL unsigned long long #define ff first #define ss second #define pb push_back #define INF 5e13 #define PI acos(-1.0) #define mk make_pair #define pii pair #define pll pair #define all(a) a.begin(),a.end() #define Unique(a) sort(all(a)),a.erase(unique(all(a)),a.end()) #define min3(a,b,c) min(a,min(b,c)) #define max3(a,b,c) max(a,max(b,c)) #define min4(a,b,c,d) min(a,min(b,min(c,d))) #define max4(a,b,c,d) max(a,max(b,max(c,d))) #define SQR(a) ((a)*(a)) #define FOR(i,a,b) for(int i=a;i<=b;i++) #define ROF(i,a,b) for(int i=a;i>=b;i--) #define REP(i,b) for(int i=0;i0){if(P%2==1){R=(R*B)%M;}P/=2;B=(B*B)%M;}return R;} LL fac[200005];void FacGen(){fac[0]=1;FOR(i,1,200000)fac[i]=(fac[i-1]*i)%MOD;} LL ara[26][100005],q; string s; int main() { FacGen(); cin >> s; s = " " + s; for(int i = 1 ;i < s.size();i++){ int d = s[i] - 'a'; for(int j = 0;j < 26;j++){ if(j == d)ara[j][i] = ara[j][i-1] + 1; else ara[j][i] = ara[j][i-1]; } } cin >> q; while(q--) { int l,r; cin >> l >> r; vectorv; LL s = 0; LL down = 1; LL ex = 0; for(int i = 0;i < 26;i++){ LL d = ara[i][r] - ara[i][l-1]; v.push_back(d); s += d/2; ex = ex + d % 2; down = (down * fac[d/2]) % MOD; } LL up = fac[s]; up = (up * BigMod(down,MOD-2,MOD))%MOD; if(ex != 0){ up = (up * ex) % MOD; } up += MOD; up %= MOD; cout << up << "\n"; } }