Farmer John chce ukryć przed krowami wiadomość: ciąg długości co najmniej 2 złożony tylko z A..Z.

Szyfruje go sekwencją operacji. Operacja na $S$ usuwa niektóre, lecz nie wszystkie, początkowe albo końcowe znaki $S$, po czym dołącza oryginalny $S$ na początku lub końcu reszty. Jedna operacja na ABC może dać te osiem ciągów:

AABC ABABC BCABC CABC ABCA ABCAB ABCBC ABCC

Dla końcowego szyfru policz sposoby utworzenia go jedną lub więcej operacjami z jakiegoś początkowego ciągu. Operacje są różne nawet przy tym samym szyfrze. Na przykład AAA z AA można otrzymać na cztery różne sposoby.

Wypisz odpowiedź modulo 2014.

Wejście

• Wiersz 1: zaszyfrowany ciąg długości najwyżej 100.

Wyjście

• Wiersz 1: liczba sposobów utworzenia ciągu jedną lub więcej kolejnymi operacjami z początkowego ciągu długości co najmniej 2, modulo 2014. Jeśli brak, wypisz zero.

Przykład

Wejście 1

ABABA

Wyjście 1

8

Uwagi

Oto sposoby utworzenia ABABA:

1. Ciąg początkowy: ABA -> AB+ABA
2. Ciąg początkowy: ABA -> ABA+BA
3. Ciąg początkowy: AB -> AB+A -> AB+ABA
4. Ciąg początkowy: AB -> AB+A -> ABA+BA
5. Ciąg początkowy: BA -> A+BA -> AB+ABA
6. Ciąg początkowy: BA -> A+BA -> ABA+BA
7. Ciąg początkowy: ABAB -> ABAB+A
8. Ciąg początkowy: BABA -> A+BABA

Autorzy zadania: Brian Dean i Lewin Gan