Hash

template <const int basis, const int mod>
class Hash {
private:
    int n, _n;
    vector<int> _hash, _powBasis;

    int _mod(ll x) {
        return ((x % mod) + mod) % mod;
    }

    int _pow(ll x, ll k) {
        if (k == 0) {
            return 1;
        } else if (k == 1) {
            return x;
        } else {
            ll t = _pow(x, k / 2);

            return _mod(_mod(t * t) * (k % 2 == 0 ? 1 : x));
        }
    }

    void count_n() {
        _n = _pow(basis, (ll)(mod - 2) * (ll)n);
    }

public:
    Hash(string &s) {
        n = s.length();

        _hash.resize(n + 1);
        _powBasis.resize(n + 1);

        _powBasis[0] = 1;
        for (int i = 0; i < n; ++i) {
            _powBasis[i + 1] = _mod((ll)_powBasis[i] * (ll)basis);
        }

        _hash[0] = 0;
        for (int i = 0; i < n; ++i) {
            _hash[i + 1] = _mod(_hash[i] + _mod((ll)s[i] * (ll)_powBasis[i]));
        }

        count_n();
    }

    int getHashSubStr(int l, int r) { // [l, r)
        return _mod((ll)_mod((ll)_mod(_hash[r] - _hash[l]) * (ll)_powBasis[n - l]) * (ll)_n);
    }
};