题目描述

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

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

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

输入格式

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

输出格式

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

样例 #1

样例输入 #1

abc

样例输出 #1

3

样例 #2

样例输入 #2

abcba

样例输出 #2

7

样例 #3

样例输入 #3

bbcdaadcba

样例输出 #3

18

提示

样例解释

样例 2 中“好的”子串为 a,b,c,b,a,bcb,abcba 共 7 个。

数据范围

• 对于 $20\%$ 的数据，$1\leq |s|\leq 30$，字符串只包含小写字母 a；
• 对于 $100\%$ 的数据，$1\leq |s|\leq 5000$，字符串由小写字母组成。