Farmer John quer esconder das vacas uma mensagem: uma string de tamanho pelo menos 2 com apenas A..Z.

Ele a cifra com uma sequência de operações. Sobre $S$, uma operação remove alguns, mas não todos, os caracteres iniciais ou finais de $S$, e depois junta a string original $S$ ao início ou fim do restante. Uma operação sobre ABC pode dar estas oito strings:

AABC ABABC BCABC CABC ABCA ABCAB ABCBC ABCC

Dada a string cifrada final, conte as formas de produzi-la com uma ou mais operações a partir de alguma string original. As operações são distintas mesmo se dão a mesma cifra. Por exemplo, há quatro formas distintas de obter AAA a partir de AA.

Imprima a resposta módulo 2014.

Entrada

• Linha 1: uma string cifrada de tamanho no máximo 100.

Saída

• Linha 1: número de formas de produzir a string com uma ou mais operações sucessivas a partir de alguma inicial de tamanho pelo menos 2, módulo 2014. Se não houver, imprima zero.

Exemplos

Entrada 1

ABABA

Saída 1

8

Explicação

Estas são as formas de produzir ABABA:

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

Créditos do problema: Brian Dean e Lewin Gan