Дана строка 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.
Выходные данные
Выведите одно число — искомую сумму.
Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-битных целых чисел на С++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.
Примечание
В первом примере значения функции при x равном «a», «aa», «aaa» и «aaaa» равны 10, 6, 3 и 1 соответственно.
Во втором примере для любого удовлетворяющего x значение функции равно 1.