You've got a string *s* = *s*<sub class="lower-index">1</sub>*s*<sub class="lower-index">2</sub>... *s*<sub class="lower-index">|*s*|</sub> of length |*s*|, consisting of lowercase English letters. There also are *q* queries, each query is described by two integers *l*<sub class="lower-index">*i*</sub>, *r*<sub class="lower-index">*i*</sub> (1 ≤ *l*<sub class="lower-index">*i*</sub> ≤ *r*<sub class="lower-index">*i*</sub> ≤ |*s*|). The answer to the query is the number of substrings of string *s*[*l*<sub class="lower-index">*i*</sub>... *r*<sub class="lower-index">*i*</sub>], which are palindromes.

String *s*[*l*... *r*] = *s*<sub class="lower-index">*l*</sub>*s*<sub class="lower-index">*l* + 1</sub>... *s*<sub class="lower-index">*r*</sub> (1 ≤ *l* ≤ *r* ≤ |*s*|) is a substring of string *s* = *s*<sub class="lower-index">1</sub>*s*<sub class="lower-index">2</sub>... *s*<sub class="lower-index">|*s*|</sub>.

String *t* is called a palindrome, if it reads the same from left to right and from right to left. Formally, if *t* = *t*<sub class="lower-index">1</sub>*t*<sub class="lower-index">2</sub>... *t*<sub class="lower-index">|*t*|</sub> = *t*<sub class="lower-index">|*t*|</sub>*t*<sub class="lower-index">|*t*| - 1</sub>... *t*<sub class="lower-index">1</sub>.
The first line contains string *s* (1 ≤ |*s*| ≤ 5000). The second line contains a single integer *q* (1 ≤ *q* ≤ 10<sup class="upper-index">6</sup>) — the number of queries. Next *q* lines contain the queries. The *i*-th of these lines contains two space-separated integers *l*<sub class="lower-index">*i*</sub>, *r*<sub class="lower-index">*i*</sub> (1 ≤ *l*<sub class="lower-index">*i*</sub> ≤ *r*<sub class="lower-index">*i*</sub> ≤ |*s*|) — the description of the *i*-th query.

It is guaranteed that the given string consists only of lowercase English letters.
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <iostream>
#include <string>
#include <map>
#include <vector>

using namespace std;
long long p = 131;
long long mod = 1000000007;
long long inv = 190839696;
long long part(long long l, long long r, long long prefx[]);
bool palindrome(long long l, long long r);

long long prefx[5005];
long long prefx2[5005];
long long pows[5005];
long long powsinv[5005];

string S;

int main() {

    cin >> S;
    long long L = S.length();

    pows[0] = 1;
    powsinv[0] = 1;
    for (int i=1; i <= 5000; i++) {
        powsinv[i] = (powsinv[i-1] * inv) % mod;
    }

    for (int i=1; i <= 5000; i++) {
        pows[i] = (pows[i-1]*p)%mod;
    }



    prefx[0] = S[0] - 'a' + 1;

    for (long long i=0; i < L; i++) { 
        prefx[i] = (prefx[i-1] + pows[i] * (S[i] - 'a' + 1)) % mod; 
    }
    
    string S2 = "";
    for (int i=L-1; i >= 0; i--) {
        S2 += S[i];
    }

    prefx2[0] = S2[0] - 'a' + 1;

    for (long long i=0; i < L; i++) { 
        prefx2[i] = (prefx2[i-1] + pows[i] * (S2[i] - 'a' + 1)) % mod; 
    }

    long long ans[5005][5005];
    long long query[5005][5005];
    for (long long i=0; i < L; i++) {
        for (long long j=i; j < L; j++) {
            if (palindrome(i, j)) {
                ans[i][j] = 1;
            }
        }
    }

    for (long long g = L-1; g > -1; g--) {
        long long counter = 0;
        for (long long y = g; y < L; y++) {
            counter += ans[g][y];
            query[g][y] = counter + query[g+1][y];
        }
    }

    long long x;
    cin >> x;
    for (long long i=0; i < x; i++) {
        long long asdf, fdsa;
        cin >> asdf >> fdsa;
        int a = query[0][0];
        

    }


    return 0;
}

long long part(long long l, long long r, long long prefx[]) {
    if (l==0) { return prefx[r]; }
    return ((prefx[r] - prefx[l-1]) * powsinv[l])%mod;
}

bool palindrome(long long l, long long r) {
    return part(l, r, prefx) == part(S.length()-r-1, S.length()-l-1, prefx2);
}