Farmer John ha un messaggio segreto da nascondere alle mucche: una stringa di lunghezza almeno 2 contenente solo A..Z.
Per cifrarlo, FJ applica una sequenza di “operazioni”. Un’operazione su $S$ prima la accorcia rimuovendo il primo o l’ultimo carattere, poi concatena la stringa originale $S$ all’inizio o alla fine. Per esempio, un’operazione su ABCD può produrre quattro stringhe:
BCDABCD ABCABCD ABCDABC ABCDBCD
Data la stringa cifrata finale, conta i modi in cui FJ potrebbe averla prodotta applicando una o più operazioni successive a una stringa originale. Le operazioni sono distinte anche se producono la stessa cifratura. Per esempio, ci sono quattro modi distinti di ottenere AAA da AA, corrispondenti alle quattro operazioni sopra.
Input
- Riga $1$: una stringa di lunghezza al massimo 100.
Output
- Riga $1$: il numero di modi distinti di produrre questa stringa applicando una o più operazioni successive a una stringa originale di lunghezza almeno 2. Se non ce ne sono, stampa zero.
Esempi
Input 1
ABABA
Output 1
6
Nota
Ecco i diversi modi di produrre ABABA:
- Iniziare con la stringa:
ABA -> AB+ABA - Iniziare con la stringa:
ABA -> ABA+BA - Iniziare con la stringa:
AB -> AB+A -> AB+ABA - Iniziare con la stringa:
AB -> AB+A -> ABA+BA - Iniziare con la stringa:
BA -> A+BA -> AB+ABA - Iniziare con la stringa:
BA -> A+BA -> ABA+BA
Autori del problema: Brian Dean e Lewin Gan