Description

Farmer John has a secret message he wants to hide from his cows; the message is a string S of length at least 2 containing only the uppercase letters A–Z.

To encrypt S, FJ applies one or more operations. In a single operation on a string S, he first shortens S by removing some (but not all) of the initial characters or some (but not all) of the final characters of S, after which the original string S is attached either to the beginning or the end. For example, applying a single operation to S = ABC can yield the following eight strings:

AABC ABABC BCABC CABC ABCA ABCAB ABCBC ABCC

Given the final encrypted string, please count the number of possible ways FJ could have produced this string using one or more operations applied to some source string. Operations are treated as distinct even if they give the same encryption of FJ’s message. For example, there are four distinct ways to obtain AAA from AA. Print your answer modulo 2014.

Input Format

• Line 1: A single encrypted string of length at most 100.

Output Format

• Line 1: The number of ways FJ could have produced this string with one or more successive operations applied to some initial string of length at least 2, written modulo 2014. If there are no such ways, output 0.

ABABA 

8 

Hint

Here are the different ways FJ could have produced ABABA:

1. Start with ABA -> AB+ABA.
2. Start with ABA -> ABA+BA.
3. Start with AB -> AB+A -> AB+ABA.
4. Start with AB -> AB+A -> ABA+BA.
5. Start with BA -> A+BA -> AB+ABA.
6. Start with BA -> A+BA -> ABA+BA.
7. Start with ABAB -> ABAB+A.
8. Start with BABA -> A+BABA.

Translated by ChatGPT 5