typedef unsigned long long ULL;
const ULL base = 131;
const int mxn = 110005;
char s[mxn];
ULL hash[mxn], power[mxn];

void deal_hash(){
    power[0] = 1;
    hash[0] = 0;
    for(int i = 1; i <= mxn-5; i++) power[i] = power[i-1] * base;
    for(int i = 1; i <= strlen(s+1); i++)   hash[i] = hash[i-1] * base + (s[i]-'0');
}

ULL get_hash1(int l, int r, ULL Hash[]){
    return Hash[r] - Hash[l-1]*power[r-l+1];
}