MPalind

#include <fstream>
#include <cstring>
#define MOD 666013
using namespace std;
ifstream fin("mpalind.in");
ofstream fout("mpalind.out");
int A[1010][1010],n,m;
char s[1010];
bool P[1010][1010];

bool palindrom(int x,int y)
{
    int i,mij=(x+y)/2;
    for(i=x;i<=mij;++i)
        if(s[i]!=s[y-i+x])
            return 0;
    return 1;
}

int main()
{
    int i,j,k,p;
    fin.getline(s,1008);
    n=strlen(s);
    for(i=0;i<n;++i)
        for(j=i;j<n;++j)
            P[i][j]=palindrom(i,j);
    for(i=0;i<n;++i)
        A[i][i]=1;
    for(k=2;k<=n;++k)
        for(i=0;i<=n-k;++i)
        {
            j=i+k-1;
            A[i][j]+=P[i][j];
            for(p=i;p<j;++p)
                if(P[i][p])
                    A[i][j]=(A[i][j]%MOD+A[p+1][j]%MOD)%MOD;
    	}
    fin>>m;
    for(i=1;i<=m;++i)
    {
        fin>>j>>k;
        fout<<A[j-1][k-1]<<'\n';
    }
    fout.close();
    return 0;
}