题目描述

​ 今天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\)中只含小写字母。