Hash

struct Hash{
    vector<ll> suf , pows;
    ll mod;

    Hash(string & s , int base = 153 , int _mod = 1000000007){
        int n = sz(s);
        suf = vector<ll>(n + 1 , 0LL);
        pows = vector<ll>(n + 1 , 0LL);
        pows[1] = base;
        mod = _mod;
        repn(i , n){
            suf[i] = (s[i] + suf[i + 1] * pows[1]) % mod;
        }
        repf(i , 2 , n + 1){
            pows[i] = (base * pows[i - 1]) % mod;
        }
    }

    ll str(int l , int r){ // [l , r]
        ll res = (suf[l] - suf[r + 1] * pows[r - l + 1]) % mod;
        while(res < 0)res += mod;
        return res % mod;
    }
};