Farmer John veut cacher un message aux vaches : une chaîne de longueur au moins 2 contenant seulement A..Z.

Il la chiffre par une suite d’opérations. Sur $S$, une opération retire une partie, mais pas tous, des caractères du début ou de la fin de $S$, puis attache la chaîne originale $S$ au début ou à la fin de la partie restante. Une opération sur ABC peut donner ces huit chaînes :

AABC ABABC BCABC CABC ABCA ABCAB ABCBC ABCC

Pour la chaîne chiffrée finale, comptez les façons de la produire par une ou plusieurs opérations depuis une certaine chaîne source. Les opérations sont distinctes même si elles donnent le même chiffrement. Par exemple, quatre façons distinctes donnent AAA depuis AA.

Affichez la réponse modulo 2014.

Entrée

• Ligne 1 : une chaîne chiffrée de longueur au plus 100.

Sortie

• Ligne 1 : le nombre de façons de produire cette chaîne par une ou plusieurs opérations successives sur une chaîne initiale de longueur au moins 2, modulo 2014. Si aucune, affichez zéro.

Exemples

Entrée 1

ABABA

Sortie 1

8

Remarque

Voici les façons de produire ABABA :

1. Chaîne initiale : ABA -> AB+ABA
2. Chaîne initiale : ABA -> ABA+BA
3. Chaîne initiale : AB -> AB+A -> AB+ABA
4. Chaîne initiale : AB -> AB+A -> ABA+BA
5. Chaîne initiale : BA -> A+BA -> AB+ABA
6. Chaîne initiale : BA -> A+BA -> ABA+BA
7. Chaîne initiale : ABAB -> ABAB+A
8. Chaîne initiale : BABA -> A+BABA

Auteurs du problème : Brian Dean et Lewin Gan