401819: GYM100534 B Fake Coins
Description
Cristiano, as a leader of his team, works in the Security Lab of Central Bank of Real Mars (SLCBRM). They want to improve security of coins that Central Bank makes. They want to use string codes that will be carved on coins to determine whether the coin is fake or original. Cris's team suggested him an amazing idea for managing security of coins. They have a base string called B and a sequence of numbers called S. They select some characters from the base string to generate the security codes. If the i-th element of sequence is Si Then the i-th element of generated code is the Si-th character of B i.e.(B[Si]). As you can clearly see the length of the generated security string code is equal to the number of elements in the sequence. Their sequences are very similar to fibonacci numbers but their first and second elements are not always 1! They select two different numbers as first and second element of sequence (first number is always less than the second number). Then the third number of sequence is the sum of first and second numbers, the forth number is the sum of third and second number and so on. This process stops when a new element is greater than the length of the sequence. All elements of the sequence must be less than or equal to length of the base string. Cris read the algorithm of generating string codes and realized that it can be some problems with same string codes. He wants to know how many different string codes can be generated using his team's algorithm. Because Criastiano is busy with scoring for Real Mars Football team he asked you to solve his problem!
InputFirst and only line of input contains the base string B(3 ≤ len(B) ≤ 1000). Base string is composed of digits, lowercase and uppercase Latin letter.
OutputPrint one line containing the number of different security string codes that can be generated using Criastiano's team algorithm.
ExamplesInputabbaOutput
5Input
abBAOutput
6Input
FAKE0123456789originalOutput
217Note
In the first sample the codes are: 1 2 3 -> "abb" 1 3 4 -> "aba" 1 4 -> "aa" 2 3 -> "bb" 3 4 -> "ba"