题目描述

​ 今天Kiana想出一道字符串题，最好是和回文串相关的那种，由于她不会出题，所以就随手写下了一个字符串$S$。
​ 贪玩的Kiana尝试翻转这个字符串的一个连续子串$s_ls_{l+1}\cdots s_{r-1}s_r$，即进行如下操作：对于字符串$S=s_1s_2\cdots s_{l-1}s_ls_{l+1}\cdots s_{r-1}s_rs_{r+1}\cdots s_{n-1}s_n$，对其翻转Kiana指定的子串$s_ls_{l+1}\cdots s_{r-1}s_r$后字符串将变为$S=s_1s_2\cdots s_{l-1}s_rs_{r-1}\cdots s_{l+1}s_ls_{r+1}\cdots s_{n-1}s_n$。聪明的Kiana还发现，对于长度为$n$的字符串，一共有$\frac{n(n+1)}{2}$个不同的子串可以翻转，真是太有趣了！
​ 但是Kiana意识到，翻转某些子串并不会得到新的子串，而翻转某些不同的子串可能会得到相同的新字符串，所以她想知道，通过翻转S的一个子串，可以得到的不同字符串数量是多少。由于Kiana自己不会算，所以希望你能够帮助她。

输入输出格式

输入格式
第一行包含一个字符串$S$，表示Kiana写下的字符串。
输出格式
输出共一行，包含一个正整数，表示翻转S的一个子串可以得到的不同字符串数量。

输入输出样例

输入样例#1：

abcd

输出样例#1：

7

输入样例#2：

turn2.in

输出样例#2：

turn2.out

样例解释

​ 在输入输出样例1中，Kiana写下的字符串为$abcd$，她有$10$种不同的翻转方法：
​ 翻转子串$s_1$，得到字符串$abcd$
​ 翻转子串$s_2$，得到字符串$abcd$
​ 翻转子串$s_3$，得到字符串$abcd$
​ 翻转子串$s_4$，得到字符串$abcd$
​ 翻转子串$s_1s_2$，得到字符串$bacd$
​ 翻转子串$s_2s_3$，得到字符串$acbd$
​ 翻转子串$s_3s_4$，得到字符串$abdc$
​ 翻转子串$s_1s_2s_3$，得到字符串$cbad$
​ 翻转子串$s_2s_3s_4$，得到字符串$adcb$
​ 翻转子串$s_1s_2s_3s_4$，得到字符串$dcba$
​ 综上所述，Kiana可能得到$abcd,bacd,acbd,abdc,cbad,adcb,dcba$，所以输出的答案为$7$。

数据范围

​ 对于$20\%$的数据，保证$1\leq|S|\leq 30$。
​ 对于$40\%$的数据，保证$1\leq|S|\leq 300$。
​ 对于$60\%$的数据，保证$1\leq|S|\leq 3000$。
​ 对于$80\%$的数据，保证$1\leq|S|\leq 300000$。
​ 对于$100\%$的数据，保证$1\leq|S|\leq 3\times 10^6$。
​ 上面每一档数据中，都有$25\%$的数据，保证$S$中只包含字母$a$和$b$，对于$100\%$的数据，保证$S$中只含小写字母。