Background

:::epigraph[------ Palindrom] Blankness is the only language that never lies. :::

Problem Description

You are playing a game called “Mirror Fragments”. In this game, you travel through an ancient ruin made of mirrors. The inscriptions in the ruin change in strange ways inside the mirrors.

You once observed that after a character sequence is reflected by a mirror, what you see looks like it is “unfolded”, and every character appears twice. For example, the sequence $\tt{hua}$ appears in the mirror as $\tt{aauuhh}$. If you look from the side and see both the real object outside the mirror and the virtual image in the mirror at the same time, they overlap in order, forming $\tt{aauuhhhua}$. This overlapped whole is the complete mapping of the sequence.

You are very interested in this mapping. Now you are given a string $S=s_1s_2\cdots s_n$ of length $n$. Please count how many non-empty substrings $T=S[l\dots r]$ (where $S[l\dots r]=s_ls_{l+1}s_{l+2}\cdots s_r$) can be an image of such a mapping. Specifically, a substring $T=t_1t_2\cdots t_m$ of length $m$ must satisfy the following conditions:

• $m$ is a multiple of $3$.
• Let $m = 3k$. Then for all $i=1,2,\dots,k$, we have $t_{2i-1}=t_{2i}=t_{3k-i+1}$.

In other words, $T$ must be of the form:

$$a_1a_1a_2a_2a_3a_3\cdots a_{k}a_{k}a_{k}a_{k-1}a_{k-2}\cdots a_1$$

where $a_1, a_2, \dots, a_k$ is some character sequence.

Note that for two substrings $S[l\dots r]=s_ls_{l+1}s_{l+2}\cdots s_r$ and $S[l'\dots r']=s_{l'}s_{l'+1}s_{l'+2}\cdots s_{r'}$, they are considered two different substrings and should be counted twice if and only if $l\ne l'$ or $r\ne r'$.

Input Format

The input consists of one line containing only a string $S$ (the length $|S|$ satisfies $1\le |S|\le 2\times 10^5$). It is guaranteed that $S$ consists only of lowercase Latin letters $\texttt{a}, \texttt{b}, \texttt{c}, \cdots, \texttt{z}$.

Output Format

Output one line containing one integer, the number of substrings that satisfy the conditions.

aaaaaa

5

aaaaaabbbcccccc

11

Hint

Translated by ChatGPT 5