Farmer John a un message secret à cacher à ses vaches : une chaîne d’au moins 2 caractères ne contenant que A..Z.

Pour le chiffrer, FJ applique une série d’« opérations ». Une opération sur une chaîne $S$ la raccourcit d’abord en supprimant son premier ou dernier caractère, puis ajoute la chaîne originale $S$ au début ou à la fin. Par exemple, une opération sur ABCD peut donner quatre chaînes :

BCDABCD ABCABCD ABCDABC ABCDBCD

Étant donnée la chaîne chiffrée finale, comptez les façons dont FJ aurait pu la produire en appliquant une ou plusieurs opérations successives à une chaîne source. Les opérations sont distinctes même si elles donnent le même chiffrement. Par exemple, quatre façons distinctes permettent d’obtenir AAA à partir de AA, correspondant aux quatre opérations ci-dessus.

Entrée

• Ligne $1$ : une chaîne d’au plus 100 caractères.

Sortie

• Ligne $1$ : le nombre de façons distinctes de produire cette chaîne par une ou plusieurs opérations successives sur une chaîne source d’au moins 2 caractères. Si aucune façon n’existe, affichez zéro.

Exemples

Entrée 1

ABABA

Sortie 1

6

Remarque

Voici les différentes façons de produire ABABA :

1. Partir de la chaîne : ABA -> AB+ABA
2. Partir de la chaîne : ABA -> ABA+BA
3. Partir de la chaîne : AB -> AB+A -> AB+ABA
4. Partir de la chaîne : AB -> AB+A -> ABA+BA
5. Partir de la chaîne : BA -> A+BA -> AB+ABA
6. Partir de la chaîne : BA -> A+BA -> ABA+BA

Auteurs du problème : Brian Dean et Lewin Gan