Rolling hash

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

const ll p=367;
const ll mod=1e9+7;
const ll N=1e5+10;

char s[N];
ll h[N], g[N], deg[N], inv[N];
int l, r, q;

ll mod_pow (ll num, ll pw)
{
    ll ret=1;
    while (pw)
    {
        if (pw&1) ret=(ret*num)%mod;
        pw>>=1;
        num=(num*num)%mod;
    }
    return ret;
}

ll mod_inv (ll num)
{
    return mod_pow(num, mod-2);
}

void rolling (int n)
{
    deg[0]=1; inv[0]=1;
    deg[1]=p; inv[1]=mod_inv(p);
    h[0]=s[0]-'a';
    g[n-1]=s[n-1]-'a';
    for (int i=2;i<n;i++)
    {
        deg[i]=(deg[i-1]*deg[1])%mod;
        inv[i]=(inv[i-1]*inv[1])%mod;
    }
    for (int i=1;i<n;i++) h[i]=(h[i-1]+(deg[i]*(s[i]-'a')%mod))%mod;
    for (int i=n-2;i>=0;i--) g[i]=(g[i+1]+(deg[n-1-i]*(s[i]-'a')%mod))%mod;
}

bool check (int l, int r, int n)
{
    ll fi=(((h[r]-h[l-1]+mod)%mod)*inv[l])%mod;
    ll se=(((g[l]-g[r+1]+mod)%mod)*inv[n-r])%mod;
    cout << fi << " " << se << endl;
    return (fi==se);
}

int main()
{
    scanf ("%s", s);
    int n=strlen(s);

    rolling(n);

    scanf ("%d", &q);
    while (q--)
    {
        scanf ("%d%d", &l, &r);
        printf ("%d\n", check(l-1, r-1, n-1));
    }

    return 0;
}