Orice șir de caractere poate fi descompus în palindromuri într-unul sau mai multe moduri. De exemplu, șirul capac poate fi descompus în 3 moduri:

• capac
• c, apa, c
• c, a, p, a, c

Cerința

Dându-se un șir de caractere format numai din litere mici, să se determine numărul de moduri de a descompune șirul în palindromuri. Pentru că acest număr poate fi mare, se va determina numărul modulo 777013

Date de intrare

Programul citește de la tastatură șirul de litere.

Date de ieșire

Programul va afișa pe ecran numărul de posibilități, modulo 777013, de a scrie șirul ca palindromuri.

Restricții și precizări

• șirul de litere este nevid și are lungimea maximă 5000

Exemplu:

Intrare

capac

Ieșire

3