class String_Hash
{

private:
    ll length;
    const ll m1 = 1e9 + 7, m2 = 1e9 + 9;
    ll p1 = 31, p2 = 37;
    vector<ll> hash1, hash2;
    pair<ll, ll> hash_pair;

public:
    inline static vector<ll> inv_pow1, inv_pow2;
    inline static ll inv_size = 1;
    ll rand(ll l, ll r)
    {
        static std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());
        std::uniform_int_distribution<int> ludo(l, r);
        return ludo(rng);
    }
    long long power(long long x, long long y, long long p)
    {
        long long result = 1;
        for (; y; y >>= 1, x = x * x % p)
        {
            if (y & 1)
            {
                result = result * x % p;
            }
        }
        return result;
    }
    long long inverse(long long x, long long p)
    {
        return power(x, p - 2, p);
    }
    String_Hash() {}
    String_Hash(const string &s)
    {
        length = s.size();
        p1 = rand(37, 1 << 10);
        p2 = rand(41, 1 << 9);
        hash1.resize(length);
        hash2.resize(length);
        ll h1 = 0, h2 = 0;
        long long p_pow1 = 1, p_pow2 = 1;
        for (ll i = 0; i < length; i++)
        {
            h1 = (h1 + (s[i] - 'a' + 1) * p_pow1) % m1;
            h2 = (h2 + (s[i] - 'a' + 1) * p_pow2) % m2;
            p_pow1 = (p_pow1 * p1) % m1;
            p_pow2 = (p_pow2 * p2) % m2;
            hash1[i] = h1;
            hash2[i] = h2;
        }
        hash_pair = make_pair(h1, h2);
        if (inv_size < length)
        {
            for (; inv_size < length; inv_size <<= 1)
                ;
            inv_pow1.resize(inv_size, -1);
            inv_pow2.resize(inv_size, -1);
            inv_pow1[inv_size - 1] = inverse(power(p1, inv_size - 1,
                                                   m1),
                                             m1);
            inv_pow2[inv_size - 1] = inverse(power(p2, inv_size - 1,
                                                   m2),
                                             m2);
            for (ll i = inv_size - 2; i >= 0 && inv_pow1[i] == -1; i--)
            {
                inv_pow1[i] = (1LL * inv_pow1[i + 1] * p1) % m1;
                inv_pow2[i] = (1LL * inv_pow2[i + 1] * p2) % m2;
            }
        }
    }
    ll size()
    {
        return length;
    }
    pair<ll, ll> prefix(const ll index)
    {
        return {hash1[index], hash2[index]};
    }
    pair<ll, ll> substr(const ll l, const ll r)
    {
        if (l == 0)
        {
            return {hash1[r], hash2[r]};
        }
        ll temp1 = hash1[r] - hash1[l - 1];
        ll temp2 = hash2[r] - hash2[l - 1];
        temp1 += (temp1 < 0 ? m1 : 0);
        temp2 += (temp2 < 0 ? m2 : 0);
        temp1 = (temp1 * 1LL * inv_pow1[l]) % m1;
        temp2 = (temp2 * 1LL * inv_pow2[l]) % m2;
        return {temp1, temp2};
    }
    bool operator==(const String_Hash &other)
    {
        return (hash_pair == other.hash_pair);
    }
};