18479번 - Three Indices 다국어

문제

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

• w₀ = w, and |w_i| = |w| when 0 < i ≤ m;
• w_i differs from w_i−1 in at most one position when 0 < i ≤ m;
• t = w₀w₁ . . . w_m.

You are given a string s = s₁s₂ . . . s_|s|. Find the number of triplets of indices (i, j, k) such that 1 ≤ i < j < k ≤ |s| and s_i..k = s_is_i+1 . . . s_k is a smooth transformation of s_i..j = s_is_i+1 . . . s_j.

입력

The only line of the input contains the string s (4 ≤ |s| ≤ 10⁵) 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).