题目描述

给定一个字符串 $s$ 。 现在，请你求一下这个串中首尾字符相同的子串数目。

输入描述

一行，一个只包括小写字母的字符串 $s(1\leq |s|\leq 10^5)$ 。

输出描述

一个整数，字符串中首尾字符相同的子串数目。

样例

输入

aaa

输出

6

样例说明

长度为 $1$ 的三个子串 "a" 长度为 $2$ 的两个子串 "aa" 长度为 $3$ 的一个子串 "aaa"