Cerința

TH este foarte pasionat de șiruri palindromuri. El are un șir de caractere ce conține litere ale alfabetului englezesc A, indexat de la 1 și își pune M întrebări de forma: “Pentru x și y, în câte moduri pot împărți șirul A[x...y] în secvențe palindrom? Acest număr poate fi foarte mare, așa că mă mulțumesc cu rezultatul modulo 666013”.

Date de intrare

Fișierul de intrare mpalind.in conține pe prima linie șirul A format din litere ale alfabetului englezesc. Pe urmatoarea linie se află numărul M, iar pe următoarele M linii se află câte două numere x și y reprezentând fiecare câte o întrebare.

Date de ieșire

Fișierul de ieșire mpalind.out va conține M linii, pe fiecare linie i aflându-se răspunsul la întrebarea i.

Restricții și precizări

• 1 ≤ lungimea șirului ≤ 1000
• 1 ≤ M ≤ 100.000
• pentru orice întrebare 1 ≤ x ≤ y ≤ lungimea șirului

Exemplu:

mpalind.in

ababcb
3
1 6
1 3
4 6

mpalind.out

5
2
2

Explicație

Pentru prima întrebare sunt 5 moduri în care se poate împărți A[1...6]:
1. (a) (b) (a) (b) (c) (b)
2. (a) (b) (a) (bcb)
3. (aba) (b) (c) (b)
4. (a) (bab) (c) (b)
5. (aba) (bcb)