Problem
O programador Vasya não teve sorte - em vez de férias, ele foi enviado em uma viagem de negócios para uma conferência científica. "Precisamos aumentar o nível de conhecimento", disse o chefe, "uma importante conferência sobre criptografia está sendo realizada na França - e lá eles criptografaram na época de Richelieu e quebraram as cifras de outras pessoas na época de Vieta."
Vasya descobriu rapidamente que já tinha visto todas as pinturas do Louvre em algum lugar, a visão da Torre Eiffel tornou-se entediante para ele antes mesmo de o mouse limpá-la do tapete, e fazemos essas pirâmides de vidro para todos os tipos de quiosques e restaurantes duvidosos. Em uma palavra, simplesmente não havia nada para ver em Paris, não havia lugar para pescar, então Vasya teve que comparecer aos relatórios da conferência.
Um dos palestrantes, mais uma vez tentando desvendar as cifras de Bacon, apresentou a hipótese de que a chave para os mistérios de Bacon pode ser encontrada analisando todas as subsequências possíveis das obras de Bacon. "Mas há muitos deles!" Vasya ficou surpreso em voz alta. "Não, nem tanto!" - gritou o orador, - "Calcule e você verá por si mesmo!"
Na mesma noite, Vasya encontrou as obras completas de Bacon na Internet. Ele escreveu um programa que convertia os textos em uma longa linha, removendo todos os espaços e sinais de pontuação dos textos. E agora Vasya está muito intrigado - como contar o número de substrings diferentes dessa string?
Entrada
A entrada contém uma string não vazia recebida por Vasya. A string consiste apenas em caracteres latinos minúsculos. Seu comprimento não excede 2.000 caracteres.
Saída
Imprime o número de diferentes substrings desta string.
Exemplos