Own_Hashing

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

#define MOD 1000000007
#define MOD1 1000000009
#define PR 43
#define PR1 37
#define ll long long
#define MAX 200005

int bigmod(ll a,ll p,int md)
{
    long long ret = 1;
    while(p) {
        if(p & 1) ret = ret * a % md;
        a = a * a % md;
        p >>= 1;
    }
    return ret;
}

int mod_mul(ll a,ll b,int md){return (a*b)%md;}
int mod_plus(ll a,ll b,int md){return (a+b)%md;}
int mod_sub(ll a,ll b,int md){a-=b;if(a<0)a+=md;return a;}

int all_hash[MAX][2],inv[MAX][2];



void calc_hash(string str)
{
    int xx,xx1,pw,pw1;
    xx=xx1=0;
    pw=pw1=1;
    for(int i=0;i<str.size();i++){
        xx=mod_plus(xx,mod_mul(pw,str[i],MOD),MOD);
        xx1=mod_plus(xx1,mod_mul(pw1,str[i],MOD1),MOD1);

        all_hash[i][0]=xx;
        all_hash[i][1]=xx1;

        inv[i][0]=bigmod(pw,MOD-2,MOD);
        inv[i][1]=bigmod(pw1,MOD1-2,MOD1);

        pw=mod_mul(pw,PR,MOD);
        pw1=mod_mul(pw1,PR1,MOD1);
    }
}

pair<int,int> substring_hash(int l,int r)
{
    if(l==0)return make_pair(all_hash[r][0],all_hash[r][1]);

    int xx= mod_sub(all_hash[r][0],all_hash[l-1][0],MOD);
    int xx1=mod_sub(all_hash[r][1],all_hash[l-1][1],MOD1);

    xx=mod_mul(xx,inv[l][0],MOD);
    xx1=mod_mul(xx1,inv[l][1],MOD1);

    return make_pair(xx,xx1);
}

int main()
{
    //freopen("input.txt","r",stdin);
    int i,j,k,t,a;

    string str;
    cin>>str;
    calc_hash(str);

    while(1){

        int l,r;
        cin>>l>>r;
        pair<int,int>p=substring_hash(l,r);
        cout<<"---->  "<<p.first<<' '<<p.second<<endl;
    }



    return 0;
}