Module: Hashes


2 /2


Theory Click to read/hide

Hashing a string is a representation of a string as some number, unique (we will assume that the chance of a collision is negligible) for each string. This allows you to store any important data (like passwords) in the database not as strings, but as numbers. This allows you to protect passwords if an attacker gains access to the password database, because he will not get the passwords themselves, but only their numerical representation, and it is almost impossible to get a string by its hash (especially without knowing the hashing algorithm). 
Polynomial hashes are most often used in programming competition problems.
One of the best ways to determine the hash function of the string S is as follows:
h(S)  =  S[0]  +  S[1] * P  +  S[2] * P^2  +  S[3] * P^3  +  ...  +  S[N] * P^N


Programmer Vasya was unlucky - instead of a vacation, he was sent on a business trip to a scientific conference. "We need to increase the level of knowledge," said the boss, "An important conference on cryptography is being held in France - and there they encrypted back in the time of Richelieu and cracked other people's ciphers back in the time of Vieta."
Vasya quickly found out that he had already seen all the Louvre paintings somewhere, the sight of the Eiffel Tower became boring to him even before the mouse wiped it off the rug, and we make such glass pyramids for all sorts of kiosks and dubious eateries. In a word, there was simply nothing to see in Paris, there was nowhere to fish, so Vasya had to attend reports at the conference.
One of the speakers, once again trying to unravel Bacon's ciphers, put forward a hypothesis that the key to Bacon's mysteries can be found by analyzing all possible substrings of Bacon's works. "But there are too many of them!" Vasya was surprised aloud. "No, not so much!" - shouted the speaker, - "Calculate, and you will see for yourself!"
The same evening, Vasya found the complete works of Bacon on the Internet. He wrote a program that converted the texts into one long line, removing all spaces and punctuation marks from the texts. And now Vasya is very puzzled - how to count the number of different substrings of this string? 

The input contains a non-empty string received by Vasya. The string consists only of lowercase Latin characters. Its length does not exceed 2000 characters. 

Print the number of different substrings of this string.


# Input Output
1 aaba 8