Programmer Vasya was down on his luck. Instead of a vacation, he was sent to a scientific conference.

“It is necessary to increase your competence,” his boss said, “it’s an important conference on cryptography, and it’s held in France, where they used encryption in the days of de Richelieu and cracked codes in the days of Viete.”

One of the talks at the conference was about the attempts to solve Bacon’s ciphers. The speaker proposed a hypothesis that the key to Bacon’s secrets could be found if all possible substrings of Bacon’s works were analyzed.

“But there are too many of them!” Vasya expressed his astonishment.

“Not as many as you think,” the speaker answered, “count them all and you’ll see it yourself.”

That evening Vasya found on the Web the complete set of Bacon’s works. He wrote a program that converted the texts into one long string by removing all linebreaks, spaces, and punctuation marks. And now Vasya is confused because he doesn’t know how to calculate the number of different substrings of this string.

You are given a nonempty string consisting of lowercase English letters. The string is no longer than 5000 symbols.

Output the number of different substrings of this string.