29175번 - Ковер 다국어

문제

Сегодня Сквидвард купил длинный рулон ткани. Он состоит из $n$ сшитых подряд кусочков ткани, каждый из которых покрашен в какой-то из 26 цветов. Будем считать этот рулон строкой $s$ длины $n,ドル причем, каждому цвету соответствует строчная буква латинского алфавита.

Сквидвард хочет вырезать из этого рулона ткани коврик для своей мамы. Для этого он выберет какой-то непрерывный непустой подотрезок этого рулона, вырежет его --- это и будет коврик для его мамы. Но это еще не все. Из оставшихся частей он хочет сшить точно такой же коврик. Для этого он хочет вырезать из левой и правой оставшихся частей по кусочку ткани и сшить их вместе в таком же порядке --- это будет коврик для него. При этом Сквидвард хочет, чтобы эти коврики были абсолютно одинаковыми --- тем самым он хочет показать маме свою любовь к ней. Ему стало интересно, сколькими способами можно вырезать коврик.

Формально говоря, он хочет выяснить, сколько существует таких пар индексов $i,ドル $j,ドル (1ドル \le i \le j \le n$), для которых найдутся такие $i_1,ドル $j_1,ドル $i_2,ドル $j_2$ (1ドル \le i_1 \le j_1 < i,ドル $j < i_2 \le j_2 \le n$), что $s[i..j] = s[i_1..j_1] + s[i_2..j_2]$. ($s[l..r]$ --- это подстрока строки $s,ドル с $l$-го символа по $r$-й символ включительно).

Сам Сквидвард не в состоянии посчитать это число, поэтому он попросил вас помочь ему.

입력

В первой строке входного файла дана строка $s$ (1ドル \le |s| \le 100,000円$), состоящая из строчных букв латинского алфавита.

출력

В единственной строке выходного файла выведите одно число --- количество способов вырезать коврик.

제한

노트

В первом примере существует единственная подходящая пара индексов (2, 3). Во втором примере существуют три подходящие пары индексов (3, 4), (5, 6) и (4, 6).