Farmer John vuole nascondere alle mucche un messaggio: una stringa di lunghezza almeno 2 con soli caratteri A..Z.

La cifra con una sequenza di operazioni. Su $S$, un’operazione rimuove alcuni, ma non tutti, i caratteri iniziali o finali di $S$, poi aggiunge la stringa originale $S$ all’inizio o alla fine del resto. Un’operazione su ABC può dare queste otto stringhe:

AABC ABABC BCABC CABC ABCA ABCAB ABCBC ABCC

Data la stringa cifrata finale, contate i modi di produrla con una o più operazioni da una qualche stringa iniziale. Le operazioni sono distinte anche con la stessa cifratura. Ad esempio, ci sono quattro modi distinti di ottenere AAA da AA.

Stampate la risposta modulo 2014.

Input

• Riga 1: una stringa cifrata di lunghezza al massimo 100.

Output

• Riga 1: numero di modi di produrre la stringa con una o più operazioni successive da una iniziale di lunghezza almeno 2, modulo 2014. Se nessuno, stampate zero.

Esempi

Input 1

ABABA

Output 1

8

Spiegazione

Ecco i modi di produrre ABABA:

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

Autori del problema: Brian Dean e Lewin Gan