题目描述

如果一个只包含小写的字符串首字母与尾字母相同，那么字符串是“好的”。

给出一个由小写字母组成的字符串 $s$，请你求出它有多少子串是“好的”。

子串：一个字符串中，任意连续的字符构成的子字符串称为子串。 例如，字符串 abc 一共包含 7 个子串，分别为：空串（不包含任何字符)，a，ab，abc，b，bc，c。注意，字符串 ac 不是 abc 的子串。

输入格式

输入共一行，一个字符串 $s$。

输出格式

输出共一行，表示 $s$ “好的”子串的个数。

abc

3

abcba

7

bbcdaadcba

18

提示

样例解释

对于第一组样例，只有 a，b，c 三个“好的”子串。

对于第二组样例，共有 a，b，c，b，a，bcb，abcba 七个“好的”子串。

数据范围

$|s|$ 表示字符串 $s$ 的长度。

对于 $20\%$ 的数据，$1 \le |s| \le 30$，字符串只包含小写字母 a。

对于 $30\%$ 的数据，$1 \le |s| \le 30$。

对于 $60\%$ 的数据，$1 \le |s| \le 500$，字符串由小写字母组成。

对于 $100\%$ 的数据，$1 \le |s| \le 5000$，字符串由小写字母组成。