Farmer John хочет скрыть от коров сообщение: строку длиной минимум 2 только из символов A..Z.

Для шифрования он выполняет последовательность операций. Операция над $S$ удаляет некоторые, но не все, начальные либо конечные символы $S$, затем приписывает исходную строку $S$ в начало или конец сокращённой. Например, одна операция над ABC даёт восемь возможных строк:

AABC ABABC BCABC CABC ABCA ABCAB ABCBC ABCC

По итоговой строке посчитайте способы её получения одной или несколькими операциями из некоторой исходной строки. Операции различны, даже если дают одинаковое шифрование. Например, из AA получить AAA можно четырьмя разными способами.

Выведите ответ по модулю 2014.

Входные данные

• Строка 1: зашифрованная строка длиной не более 100.

Выходные данные

• Строка 1: число способов получить строку одной или несколькими последовательными операциями из начальной строки длиной минимум 2, по модулю 2014. Если способов нет, выведите ноль.

Примеры

Входные данные 1

ABABA

Выходные данные 1

8

Примечание

Способы получить ABABA:

1. Начальная строка: ABA -> AB+ABA
2. Начальная строка: ABA -> ABA+BA
3. Начальная строка: AB -> AB+A -> AB+ABA
4. Начальная строка: AB -> AB+A -> ABA+BA
5. Начальная строка: BA -> A+BA -> AB+ABA
6. Начальная строка: BA -> A+BA -> ABA+BA
7. Начальная строка: ABAB -> ABAB+A
8. Начальная строка: BABA -> A+BABA

Авторы задачи: Brian Dean и Lewin Gan