Задача A. Префикс-функция

Входной файл:input.txt   Ограничение времени:1 сек
Выходной файл:output.txt   Ограничение памяти:256 Мб

Условие

Дана строка s. Найдите сумму значений префикс-функции для всех позиций строки s.

Формат входного файла

Во входном файле записана единственная строка s.

Формат выходного файла

В выходной файл выведите одно число — ответ на задачу.

Ограничения

1 ≤ |s| ≤ 150000

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
abcaabacabc
11

0.121s 0.018s 15