#include<bits/stdc++.h>
using namespace std;
 
#define p 101
#define MOD 1000000007
struct Query
{
    int L, R;
};
bool isPalindrome(string s, int L, int R)
{
    while (R > L)
        if (s[L++] != s[R--])
            return(false);
    return(true);
}
unsigned long long int modPow(unsigned long long int base,
                              unsigned long long int exponent)
{
    if (exponent == 0)
        return 1;
    if (exponent == 1)
        return base;
 
    unsigned long long int temp = modPow(base, exponent/2);
 
    if (exponent %2 ==0)
        return (temp%MOD * temp%MOD) % MOD;
    else
        return ((( temp%MOD * temp%MOD)%MOD) * base%MOD) % MOD;
}
unsigned long long int findMMI(unsigned long long int n)
{
    return modPow(n, MOD-2);
}
void computePrefixHash(string s, int n, unsigned long long
                       int prefix[], unsigned long long int power[])
{
    prefix[0] = 0;
    prefix[1] = s[0];
 
    for (int i=2; i<=n; i++)
        prefix[i] = (prefix[i-1]%MOD +
                    (s[i-1]%MOD * power[i-1]%MOD)%MOD)%MOD;
 
    return;
}
 
void computeSuffixHash(string s, int n,
                       unsigned long long int suffix[],
                       unsigned long long int power[])
{
    suffix[0] = 0;
    suffix[1] = s[n-1];
 
    for (int i=n-2, j=2; i>=0 && j<=n; i--,j++)
        suffix[j] = (suffix[j-1]%MOD +
                     (s[i]%MOD * power[j-1]%MOD)%MOD)%MOD;
    return;
}
void queryResults(string s, Query q[], int m, int n,
                  unsigned long long int prefix[],
                  unsigned long long int suffix[],
                  unsigned long long int power[])
{
    for (int i=0; i<=m-1; i++)
    {
        int L = q[i].L;
        int R = q[i].R;
        unsigned long long hash_LR =
            ((prefix[R+1]-prefix[L]+MOD)%MOD *
             findMMI(power[L])%MOD)%MOD;
        unsigned long long reverse_hash_LR =
            ((suffix[n-L]-suffix[n-R-1]+MOD)%MOD *
             findMMI(power[n-R-1])%MOD)%MOD;
        if (hash_LR == reverse_hash_LR )
        {
            if (isPalindrome(s, L, R) == true)
                printf("The Substring [%d %d] is a "
                       "palindrome\n", L, R);
            else
                printf("The Substring [%d %d] is not a "
                       "palindrome\n", L, R);
        }
 
        else
            printf("The Substring [%d %d] is not a "
                   "palindrome\n", L, R);
    }
 
    return;
}
 
void computePowers(unsigned long long int power[], int n)
{
    // 101^0 = 1
    power[0] = 1;
 
    for(int i=1; i<=n; i++)
        power[i] = (power[i-1]%MOD * p%MOD)%MOD;
 
    return;
}
 

int main()
{
    string s = "week";
    int n = s.length();
 
    unsigned long long int power[n+1];
 
    computePowers(power, n);
 
    unsigned long long int prefix[n+1], suffix[n+1];
 
    computePrefixHash(s, n, prefix, power);
    computeSuffixHash(s, n, suffix, power);
 
    Query q[] = {{2, 0}, {1,4}, {2, 3}};
    int m = sizeof(q)/sizeof(q[0]);
 
    queryResults(s, q, m, n, prefix, suffix, power);
    return (0);
}