Problem 3: Secret Code [Brian Dean and Lewin Gan]
У Фермера Джона есть секретное сообщение, которое он хочет зашифровать от своих коров. Сообщение – это строка, которая содержит не менее двух символов A..Z.
Чтобы зашифровать его, ФД применяет последовательность «операций» к нему. Операция, применённая к строке S, сначала сокращает S, удалив из неё некоторое количество символов сначала (но не все) или некоторое количество символов с конца (но не все), после чего добавляет исходную строку в начало или конец. Например, одна операция, применённая к строке ABC может дать 8 возможных строк:
AABC ABABC BCABC CABC ABCA ABCAB ABCBC ABCC
По заданной зашифрованной строке подсчитайте количество возможных способов создать такую строку применив одну или более операций к некоторой исходной строке. Операции считаются различными, даже если результат их выполнения одна и та же строка. Например, имеются 4 различных способа получить строку AAA из строки AA, соответствующих 4 возможным операциям, описанным выше.
Выведите ответ по модулю 2014.
PROBLEM NAME: scode
Формат входных данных
* Строка 1: строка с длиной не более 100.
Формат выходных данных
* Line 1: Количество различных способов, которыми ФД может получить эту строку, применяя одну или более последовательных операций к строке с длиной не менее 2, выведенное по модулю 2014. Если не существует таких способов, выводите 0.
Примечание
Имеется 8 способов получить строку ABABA: 1. Начиная с ABA -> AB+ABA 2. Начиная с ABA -> ABA+BA 3. Начиная с AB -> AB+A -> AB+ABA 4. Начиная с AB -> AB+A -> ABA+AB 5. Начиная с BA -> A+BA -> AB+ABA 6. Начиная с BA -> A+BA -> ABA+AB 7. Начиная с ABAB -> ABAB+A 8. Начиная с BABA -> A+BABA
Примеры
| № | Входные данные | Выходные данные |
|
1
|
ABABA
|
8
|