#include #include #include #define MOD 1000000007ll #define ull long long using namespace std; int T[100100][26]; long long F[100100]; ull euclid(ull a, ull b, ull& rx, ull& ry) { if (!b) return rx=1, ry=0, a; ull q = a/b; ull x, y; ull g = euclid(b, a-q*b, x, y); return rx=y, ry=x-q*y, g; } ull invert(ull a, ull p) { ull inverse, temp; euclid(a, p, inverse, temp); return (inverse%p+p)%p; } int main() { F[0] = 1; for(long long i=1; i<=100010; i++) F[i] = (F[i-1] * i) % MOD; string s; while(cin >> s) { memset(T, 0, sizeof T); for(int i=0; i> Q; for(int i=0; i> L >> R; long long div2 = 0, mod2 = 0, rem = 1; for(int j=0; j<26; j++) { int v = T[R][j] - T[L-1][j]; div2 += v/2; mod2 += (v%2 ? 1 : 0); rem *= F[v/2]; rem %= MOD; } long long answer = F[div2]; answer *= max(mod2, 1ll); answer %= MOD; answer *= invert(rem, MOD); answer %= MOD; // cout << " " << div2 << " " << mod2 << " " << rem << endl; cout << answer << endl; } } }