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?
Input
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.
Output
Print the number of different substrings of this string.
Examples