카펫

오늘 스퀴드워드가 긴 두루마리 천을 샀다. 이 천은 26가지 색 중 하나로 염색된 $n$개의 천 조각을 한 줄로 이어 붙인 것이다. 이 두루마리를 길이가 $n$인 문자열 $s$로 본다. 각 색은 영문 소문자 하나에 대응한다.

스퀴드워드는 이 두루마리에서 엄마에게 줄 매트를 자르려고 한다. 두루마리에서 비어 있지 않은 연속 구간을 골라 잘라내면 그것이 엄마의 매트가 된다. 나머지 부분에서는 완전히 같은 매트를 만들고 싶어 한다. 왼쪽 남은 부분에서 천 조각을 하나, 오른쪽 남은 부분에서 천 조각을 하나 잘라 그 순서대로 이어 붙인다. 그 결과가 그의 매트다. 두 매트는 완전히 같아야 한다. 매트를 자르는 방법의 수를 구하라.

형식적으로 말하면, 다음 조건을 만족하는 인덱스 쌍 $i$, $j$ ($1 \le i \le j \le n$)의 개수를 세라. $1 \le i_1 \le j_1 < i$이고 $j < i_2 \le j_2 \le n$인 $i_1$, $j_1$, $i_2$, $j_2$가 존재하여 $s[i..j] = s[i_1..j_1] + s[i_2..j_2]$가 성립해야 한다. 여기서 $+$는 문자열 연결이다.

스퀴드워드는 이 값을 직접 계산하지 못해서 당신에게 도움을 청했다.

첫 줄에 문자열 $s$ ($1 \le |s| \le 100000$)가 주어진다. $s$는 영문 소문자로만 이루어져 있다.

매트를 자르는 방법의 수를 한 줄에 출력한다.

첫 번째 예제에서는 인덱스 쌍 (2, 3)만 조건을 만족한다. 두 번째 예제에서는 (3, 4), (5, 6), (4, 6) 세 쌍이 조건을 만족한다.