int c = 37;
int mod = 1000*1000*1000+3777;

struct hashed_string{

    vector<long long> h;
    vector<long long> rh;
    vector<long long> pows;
    int n;

    hashed_string(string s){
        n = s.length();
        h.assign(n, 0);
        rh.assign(n, 0);
        pows.assign(n, 1);
        h[0] = s[0]-'a'+1;
        rh[0] = s[n-1]-'a'+1;
        for (int i = 1; i<n; i++){
            pows[i] = (pows[i-1]*c)%mod;
            h[i] = (h[i-1]*c+(s[i]-'a'+1))%mod;
            rh[i] = (rh[i-1]*c+(s[n-1-i]-'a'+1))%mod;
        }
    }

    long long get_hash(int l, int r){
        if (l==0){
            return h[r];
        } else {
            return ((h[r]-(h[l-1]*pows[r-l+1]))%mod+mod)%mod;
        }
    }

    long long get_reverse_hash(int l, int r){
        if (r==n-1){
             return rh[n-l-1];
        } else {
            return ((rh[n-l-1]-(rh[n-r-2]*pows[r-l+1]))%mod+mod)%mod;
        }
    }

    bool is_palindrome(int l, int r){
        if (l==r) return true;
        if ((r-l+1)%2==0){
            return (get_hash(l, (l+r)/2)==get_reverse_hash((l+r)/2+1, r));
        } else {
            return (get_hash(l, (l+r)/2-1)==get_reverse_hash((l+r)/2+1, r));
        }
    }

};