题目背景

社团整理了一串只包含小写英文字母的记录串。老师想统计其中有多少段连续片段满足一个简单条件：片段的第一个字符和最后一个字符相同。

题目描述

给定字符串 $S$，请统计有多少个非空连续子串的首尾字符相同。

连续子串必须是原字符串中连续的一段字符。

输入格式

输入一行字符串 $S$，仅由小写英文字母组成。

输出格式

输出一个整数，表示首尾字符相同的非空连续子串数量。

样例

abc

3

abcba

7

bbcdaadcba

18

提示

样例解释

样例 $1$ 中，满足条件的只有 a、b、c。

样例 $2$ 中，满足条件的子串有 a、b、c、b、a、bcb、abcba，共 $7$ 个。

数据范围

设 $|S|$ 表示字符串 $S$ 的长度。

• 对于 $60\%$ 的数据，$1 \le |S| \le 5000$。
• 对于 $100\%$ 的数据，$1 \le |S| \le 1000000$。
• $S$ 仅由小写字母组成。