Farmer John quiere ocultar a las vacas un mensaje: una cadena de longitud al menos 2 con solo A..Z.

La cifra mediante una secuencia de operaciones. Sobre $S$, una operación elimina algunos, pero no todos, los caracteres iniciales o finales de $S$, y luego une la cadena original $S$ al principio o al final de lo restante. Una operación sobre ABC produce estas ocho cadenas posibles:

AABC ABABC BCABC CABC ABCA ABCAB ABCBC ABCC

Dada la cadena cifrada final, cuenta las formas de producirla con una o más operaciones desde alguna cadena original. Las operaciones son distintas aunque den el mismo cifrado. Por ejemplo, hay cuatro formas distintas de obtener AAA desde AA.

Imprime la respuesta módulo 2014.

Entrada

• Línea 1: una cadena cifrada de longitud como máximo 100.

Salida

• Línea 1: número de formas de producir la cadena con una o más operaciones sucesivas desde alguna inicial de longitud al menos 2, módulo 2014. Si no hay formas, imprime cero.

Ejemplos

Entrada 1

ABABA

Salida 1

8

Nota

Estas son las formas de producir ABABA:

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

Autores del problema: Brian Dean y Lewin Gan