Secret Message Encryption

Farmer John has a secret message S which is a string of at least 2 uppercase letters (A–Z). In order to hide the message from his cows, he encrypts it by applying a sequence of one or more operations. In each operation, he takes the current string S and forms a new string as follows:

• Choose either to remove some (but not all) of the initial characters of S or some (but not all) of the final characters of S. Let the remaining substring be T (note that 1 \le |T| < |S|).
• Then attach the original string S to T: either as S+T or T+S.

For example, if S = ABC, a single operation can produce any of the following 8 distinct strings:

AABC
ABABC
BCABC
CABC
ABCA
ABCAB
ABCBC
ABCC

Given the final encrypted string F, count the number of distinct ways FJ could have produced F by applying one or more operations starting from some original secret message (which is allowed to be any string of length at least 2 consisting only of A–Z). Note that operations are considered distinct even if they yield the same encrypted string. For instance, there are 4 distinct ways to encrypt AA into AAA.

Since the answer can be very large, output it modulo \(2014\). (All formulas in this problem are rendered in LaTeX.)

The reverse process can be understood as follows. Suppose an operation transforms string \(S\) into \(F\). Then either:

• There is a split \(F = S \frown T\) with \(T \neq \emptyset\) and \(T\) equals the prefix of \(S\) (i.e. \(T = S[0:|T|]\)) and \(|T| < |S|\), or
• There is a split \(F = T \frown S\) with \(T \neq \emptyset\) and \(T\) equals the suffix of \(S\) (i.e. \(T = S[|S|-|T|:|S|]\)) and \(|T| < |S|\).

Each valid decomposition corresponds to 2 distinct operations (depending on whether \(S\) is attached at the beginning or at the end). By recursively reversing the operations and taking as the base case a valid original message (which is any string of length at least 2 that cannot be decomposed further), one can count the number of ways to obtain \(F\). Your task is to implement this logic.

inputFormat

The input consists of a single line containing the encrypted string F (a nonempty string of uppercase letters, and at least one encryption operation is applied so that \(|F| \geq 3\) in many cases, though the original secret message has length at least 2).

outputFormat

Output a single integer, the number of distinct ways to obtain \(F\) by a sequence of one or more operations, taken modulo \(2014\).

sample

AAA

4