Farmer John ma tajną wiadomość, którą chce ukryć przed krowami: napis długości co najmniej 2 zawierający tylko znaki A..Z.

Aby go zaszyfrować, FJ stosuje ciąg „operacji”. Operacja na $S$ najpierw skraca napis przez usunięcie pierwszego lub ostatniego znaku, a potem dołącza oryginalny napis $S$ na początku lub końcu. Na przykład jedna operacja na ABCD może dać cztery napisy:

BCDABCD ABCABCD ABCDABC ABCDBCD

Dla końcowego zaszyfrowanego napisu policz sposoby, na jakie FJ mógł go uzyskać przez jedną lub więcej kolejnych operacji na pewnym napisie początkowym. Operacje są różne nawet wtedy, gdy dają to samo szyfrowanie. Na przykład istnieją cztery różne sposoby uzyskania AAA z AA, odpowiadające czterem operacjom powyżej.

Wejście

• Wiersz $1$: napis długości co najwyżej 100.

Wyjście

• Wiersz $1$: liczba różnych sposobów otrzymania tego napisu przez jedną lub więcej kolejnych operacji na pewnym napisie początkowym długości co najmniej 2. Jeśli nie ma żadnego sposobu, wypisz zero.

Przykład

Wejście 1

ABABA

Wyjście 1

6

Uwagi

Oto różne sposoby uzyskania ABABA:

1. Zacznij od napisu: ABA -> AB+ABA
2. Zacznij od napisu: ABA -> ABA+BA
3. Zacznij od napisu: AB -> AB+A -> AB+ABA
4. Zacznij od napisu: AB -> AB+A -> ABA+BA
5. Zacznij od napisu: BA -> A+BA -> AB+ABA
6. Zacznij od napisu: BA -> A+BA -> ABA+BA

Autorzy zadania: Brian Dean i Lewin Gan