Three Indices

i<j<k이고 s[i..k]가 s[i..j]의 매끄러운 변환일 때, 즉 뒤쪽 문자열이 이전 문자열과 많아야 한 위치만 다른 문자열들의 연쇄일 때 그러한 삼중항의 개수를 센다.

어려움8문자열문자열 매칭구현조합론아직 제출이 없습니다시간 제한2초메모리 제한512 MB

문제 설명

예제1

문제

A string t is called a smooth transformation of a string w if there exist an integer m ≥ 1 and strings w0, w1, . . . , wm such that:

w0 = w, and |wi| = |w| when 0 < i ≤ m;
wi differs from wi−1 in at most one position when 0 < i ≤ m;
t = w0w1 . . . wm.

You are given a string s = s1s2 . . . s|s|. Find the number of triplets of indices (i, j, k) such that 1 ≤ i < j < k ≤ |s| and si..k = sisi+1 . . . sk is a smooth transformation of si..j = sisi+1 . . . sj.

입력

The only line of the input contains the string s (4 ≤ |s| ≤ 105) consisting of lowercase English letters.

출력

Display the sought number of triplets.

힌트

In the example test case, the triplets are (1, 3, 6), (3, 4, 6), (3, 4, 8), (4, 5, 7), and (5, 6, 8).