Untitled

struct haash {
    const ll B = 149;
    ll MOD;

    vll b, h;
    int n;

    haash() {}

    void build_haash(const string &s, ll _MOD = 1e9+7) {
        n = s.size();
        MOD = _MOD;

        b.resize(n + 1);
        h.resize(n + 1);

        b[0] = 1;
        h[0] = 0;

        for (int i = 0; i < n; i++) {
            b[i + 1] = b[i] * B % MOD;
            h[i + 1] = (h[i] * B + s[i]) % MOD;
        }
    }

    ll operator()(int l, int r) {
        return (h[r] - (h[l] * b[r - l]) % MOD + MOD) % MOD;
    }
};