背景

:::epigraph[------ 帕林多姆] 空白是唯一不会说谎的语言。 :::

题目描述

你正在玩一款被称为「Mirror Fragments」的游戏。在这个游戏里，你穿行于一座由镜面构筑的古老遗迹。遗迹中的铭文会在镜中发生奇异的变化。

你曾观察到一段字符序列经过镜面反射后，看到的内容会像被「展开」一样，每个字符都重复出现两次。比如，序列 $\tt{hua}$ 在镜中会呈现出 $\tt{aauuhh}$ 的形态。若从侧方同时观察镜外原物与镜中虚像，两者会前后叠加，形成 $\tt{aauuhhhua}$。这种叠加后的整体，便是该序列的完整映射。

你对这样的映射关系很感兴趣。现在给定一个长度为 $n$ 的字符串 $S=s_1s_2\cdots s_n$，请你统计其中有多少个非空子串 $T=S[l\dots r]$（其中，$S[l\dots r]=s_ls_{l+1}s_{l+2}\cdots s_r$）可以成为这样的映射的像。具体地，长度为 $m$ 的子串 $T=t_1t_2\cdots t_m$ 需要满足以下条件：

• $m$ 是 $3$ 的倍数；
• 设 $m = 3k$，则对于所有 $i=1,2,\dots,k$ 都有 $t_{2i-1}=t_{2i}=t_{3k-i+1}$。

换而言之，$T$ 必须形如：

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

其中，$a_1, a_2, \dots, a_k$ 是某个字符序列。

请注意，对于两个子串 $S[l\dots r]=s_ls_{l+1}s_{l+2}\cdots s_r$ 和 $S[l'\dots r']=s_{l'}s_{l'+1}s_{l'+2}\cdots s_{r'}$，被视为两个不同的子串，需要被统计两次，当且仅当 $l\ne l'$ 或者 $r\ne r'$。

输入格式

输入共一行，仅包含一个字符串 $S$（字符串 $S$ 的长度 $|S|$ 满足 $1\le |S|\le 2\times 10^5$）。保证 $S$ 仅由小写拉丁字母 $\texttt{a}, \texttt{b}, \texttt{c}, \cdots, \texttt{z}$ 构成。

输出格式

输出一行，仅包含一个整数，表示满足题目条件的子串个数。

aaaaaa

5

aaaaaabbbcccccc

11