시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 0 0 0 0.000%

문제

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.

예제 입력 1

abcababc

예제 출력 1

5

힌트

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