Farmer John tem uma mensagem secreta que quer esconder das vacas: uma cadeia de comprimento pelo menos 2 que só contém A..Z.
Para a cifrar, FJ aplica uma sequência de “operações”. Uma operação sobre $S$ começa por encurtá-la, removendo o primeiro ou o último carácter, e depois concatena a cadeia original $S$ no início ou no fim. Por exemplo, uma operação sobre ABCD pode dar quatro cadeias:
BCDABCD ABCABCD ABCDABC ABCDBCD
Dada a cadeia cifrada final, conte as formas de FJ a produzir aplicando uma ou mais operações sucessivas a alguma cadeia original. As operações são distintas mesmo que produzam a mesma cifra. Por exemplo, há quatro formas distintas de obter AAA a partir de AA, correspondentes às quatro operações acima.
Entrada
- Linha $1$: uma cadeia de comprimento no máximo 100.
Saída
- Linha $1$: o número de formas distintas de produzir esta cadeia através de uma ou mais operações sucessivas sobre alguma cadeia original de comprimento pelo menos 2. Se não houver nenhuma, imprima zero.
Exemplos
Entrada 1
ABABA
Saída 1
6
Nota
Estas são as diferentes formas de produzir ABABA:
- Começar com a cadeia:
ABA -> AB+ABA - Começar com a cadeia:
ABA -> ABA+BA - Começar com a cadeia:
AB -> AB+A -> AB+ABA - Começar com a cadeia:
AB -> AB+A -> ABA+BA - Começar com a cadeia:
BA -> A+BA -> AB+ABA - Começar com a cadeia:
BA -> A+BA -> ABA+BA
Autores do problema: Brian Dean e Lewin Gan