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 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] = 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;
                //if (P[p + 1][j])
                    //A[i][j] = (A[i][j] % MOD + A[i][p] % MOD) % MOD;
            }
        }
    }
    fin >> m;
    for (i = 1; i <= m; i++)
    {
        fin >> j >> k;
        fout << A[j - 1][k - 1] << '\n';
    }
    fout.close();
    return 0;
}

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;
}