F. Звёздочки и подстроки
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Рассмотрим строку $$$s$$$ из $$$n$$$ маленьких английских букв. Пусть $$$t_i$$$ — строка, полученная из $$$s$$$ заменой $$$i$$$-го символа на символ звёздочки *. Например, если $$$s = \mathtt{abc}$$$, то $$$t_1 = \tt{*bc}$$$, $$$t_2 = \tt{a*c}$$$ и $$$t_3 = \tt{ab*}$$$.

По данной строке $$$s$$$ определите количество различных строк из маленьких латинских букв и звёздочек, которые встречаются как подстроки хотя бы в одной из строк $$$\{s, t_1, \ldots, t_n \}$$$. Пустая строка входит в ответ.

Обратите внимание, что * в данной задаче является обычным символом и не играет специальной роли, как например, в подстановке регулярных выражений.

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

В единственной строке записана строка $$$s$$$ из $$$n$$$ маленьких английских букв ($$$1 \leq n \leq 10^5$$$).

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

Выведите одно число — количество различных подстрок $$$s, t_1, \ldots, t_n$$$.

Пример
Входные данные
abc
Выходные данные
15
Примечание

В примере различными подстроками являются: (пустая строка), a, b, c, *, ab, a*, bc, b*, *b, *c, abc, ab*, a*c, *bc.