#include #define fore(x,a,b) for(int x=a, qwert=b; x> s; fore(x,0,SZ(s))cnt[s[x]-'a'][x]++; fore(x,0,26)fore(y,1,SZ(s))cnt[x][y]+=cnt[x][y-1]; fact[0]=1; fore(x,1,N)fact[x]=((ll)x*fact[x-1])%M; int Q; cin >> Q; while(Q--){ int l, r, cs[26]={}; cin >> l >> r; r--; l--; fore(x,0,26) cs[x] = cnt[x][r] - (l ? cnt[x][l-1] : 0); int len = 0, impars=0; fore(x,0,26) len += cs[x]/2, impars += cs[x]%2, cs[x]/=2; ll ans = (fact[len] * max(1LL,(ll)impars))%M; fore(x,0,26) ans = (ans * be(fact[cs[x]],M-2))%M; cout << ans << "\n"; } }