Secret Code

Time limit1sMemory limit128 MB

Summary

Count the sequences of operations that build the given string from a source of length at least 2 by gluing each string to a copy missing one end character.

Level: Medium6 of 10
Topics: Dynamic programming, String matching, Recursion
Solved: No attempts yet

Problem

Farmer John has a secret message that he wants to hide from his cows. The message is a string of length at least 2 that contains only the characters A to Z.

To encrypt the message he applies a sequence of operations. One operation on a string $S$ first shortens $S$ by deleting either its first or its last character, then attaches the original string $S$ to the front or to the back of what is left. Applying one operation to ABCD gives these four results:

BCDABCD
ABCABCD
ABCDABC
ABCDBCD

You are given the final encrypted string. Count how many ways Farmer John could have produced it by applying one or more operations to some source string of length at least 2. Two operations count as different even when they produce the same string. For example, there are four different ways to obtain AAA from AA, one for each of the four operations above.

Input

The first line contains a string of length at most 100. The string contains only the characters A to Z.

Output

Print the number of different ways Farmer John could have produced the given string by applying one or more successive operations to some source string of length at least 2. If there is no such way, print 0.

Hint

For the string ABABA the six ways are:

Start with ABA -> AB+ABA
Start with ABA -> ABA+BA
Start with AB -> AB+A -> AB+ABA
Start with AB -> AB+A -> ABA+BA
Start with BA -> A+BA -> AB+ABA
Start with BA -> A+BA -> ABA+BA

Examples2

Example 1
Input
```
ABABA
```
Expected output
```
6
```
Example 2
Input
```
AAA
```
Expected output
```
4
```