Farmer John möchte eine Nachricht vor Kühen verbergen: eine Zeichenkette mit mindestens 2 Zeichen nur aus A..Z.

Er verschlüsselt sie durch Operationen. Eine Operation auf $S$ entfernt einige, aber nicht alle, Anfangs- oder Endzeichen von $S$ und hängt danach die ursprüngliche Zeichenkette $S$ vorn oder hinten an den Rest. Eine Operation auf ABC kann diese acht Zeichenketten ergeben:

AABC ABABC BCABC CABC ABCA ABCAB ABCBC ABCC

Zähle für die endgültige Verschlüsselung die Möglichkeiten, sie durch eine oder mehrere Operationen aus irgendeiner Ausgangszeichenkette zu erhalten. Operationen sind verschieden, selbst wenn die Verschlüsselung gleich ist. Aus AA entsteht AAA beispielsweise auf vier verschiedene Arten.

Gib die Antwort modulo 2014 aus.

Eingabe

• Zeile 1: eine verschlüsselte Zeichenkette mit höchstens 100 Zeichen.

Ausgabe

• Zeile 1: die Anzahl Möglichkeiten durch eine oder mehrere aufeinanderfolgende Operationen aus einer Ausgangszeichenkette mit mindestens 2 Zeichen, modulo 2014. Falls keine existiert, gib null aus.

Beispiele

Eingabe 1

ABABA

Ausgabe 1

8

Hinweis

Dies sind die Möglichkeiten für ABABA:

1. Ausgangszeichenkette: ABA -> AB+ABA
2. Ausgangszeichenkette: ABA -> ABA+BA
3. Ausgangszeichenkette: AB -> AB+A -> AB+ABA
4. Ausgangszeichenkette: AB -> AB+A -> ABA+BA
5. Ausgangszeichenkette: BA -> A+BA -> AB+ABA
6. Ausgangszeichenkette: BA -> A+BA -> ABA+BA
7. Ausgangszeichenkette: ABAB -> ABAB+A
8. Ausgangszeichenkette: BABA -> A+BABA

Aufgabenautoren: Brian Dean und Lewin Gan