D. Строка
ограничение по времени на тест
2 seconds
ограничение по памяти на тест
256 megabytes
ввод
stdin
вывод
stdout

Дана строка s. Каждой паре чисел l и r, удовлетворяющих условию 1 ≤ l ≤ r ≤ |s|, соответствует подстрока строки s, начинающаяся в позиции l и заканчивающаяся в позиции r (включительно).

Определим функцию от двух строк F(x, y) следующим образом. Найдем список таких пар чисел, для которых соответствующие подстроки строки x равны строке y. Отсортируем этот список пар по возрастанию первого числа в паре. Значение функции F(x, y) равно количеству непустых непрерывных подпоследовательностей в списке.

Например: F(babbabbababbab, babb) = 6. Список пар:

(1, 4), (4, 7), (9, 12)

Его непрерывные подпоследовательности:

  • (1, 4)
  • (4, 7)
  • (9, 12)
  • (1, 4), (4, 7)
  • (4, 7), (9, 12)
  • (1, 4), (4, 7), (9, 12)

Для заданной строки s требуется подсчитать сумму F(s, x) для всех x, принадлежащих множеству всех подстрок строки s.

Входные данные

В единственной строке находится данная строка s, которая состоит только из маленьких латинских букв (1 ≤ |s| ≤ 105).

Выходные данные

Выведите одно число — искомую сумму.

Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-битных целых чисел на С++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.

Примеры
Входные данные
aaaa
Выходные данные
20
Входные данные
abcdef
Выходные данные
21
Входные данные
abacabadabacaba
Выходные данные
188
Примечание

В первом примере значения функции при x равном «a», «aa», «aaa» и «aaaa» равны 10, 6, 3 и 1 соответственно.

Во втором примере для любого удовлетворяющего x значение функции равно 1.