Farmer John hat eine geheime Nachricht, die er vor seinen Kühen verbergen möchte: eine Zeichenkette mit mindestens 2 Zeichen, die nur A..Z enthält.

Zum Verschlüsseln führt FJ eine Folge von „Operationen“ aus. Eine Operation auf $S$ verkürzt die Zeichenkette zuerst durch Entfernen des ersten oder letzten Zeichens und fügt dann die ursprüngliche Zeichenkette $S$ am Anfang oder Ende an. Eine Operation auf ABCD kann beispielsweise vier Zeichenketten ergeben:

BCDABCD ABCABCD ABCDABC ABCDBCD

Zähle für die gegebene endgültig verschlüsselte Zeichenkette, auf wie viele Arten FJ sie durch eine oder mehrere aufeinanderfolgende Operationen auf einer Ausgangszeichenkette erzeugen könnte. Operationen zählen als unterschiedlich, auch wenn sie dieselbe Verschlüsselung ergeben. Beispielsweise gibt es vier unterschiedliche Arten, AAA aus AA zu erzeugen, entsprechend den vier Operationen oben.

Eingabe

• Zeile $1$: eine Zeichenkette mit höchstens 100 Zeichen.

Ausgabe

• Zeile $1$: die Anzahl unterschiedlicher Arten, diese Zeichenkette mit einer oder mehreren aufeinanderfolgenden Operationen aus einer Ausgangszeichenkette mit mindestens 2 Zeichen zu erzeugen. Falls es keine gibt, gib null aus.

Beispiele

Eingabe 1

ABABA

Ausgabe 1

6

Hinweis

Die verschiedenen Arten, ABABA zu erzeugen, sind:

1. Beginne mit der Zeichenkette: ABA -> AB+ABA
2. Beginne mit der Zeichenkette: ABA -> ABA+BA
3. Beginne mit der Zeichenkette: AB -> AB+A -> AB+ABA
4. Beginne mit der Zeichenkette: AB -> AB+A -> ABA+BA
5. Beginne mit der Zeichenkette: BA -> A+BA -> AB+ABA
6. Beginne mit der Zeichenkette: BA -> A+BA -> ABA+BA

Autoren der Aufgabe: Brian Dean und Lewin Gan