该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

球球最近迷上了字符串游戏，如果一串只有小写字符的且第一个字符与最后一个字符首尾相同，那么这个字符串是“幸运字符串”。

球球得到一个新的字符串 $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$，字符串由小写字母组成。