N. Пары подстрок

Посчитайте количество пар подстрок $(s_1, s_2)$ равной длины, для которых $s_1 < s_2$ лексикографически. Подстроки различаются по положению: два одинаковых куска в разных местах - это разные подстроки.

Одна строка из строчных латинских букв длиной не больше 4000.

Выведите количество пар подстрок равной длины, у которых первая лексикографически меньше второй.