Lulu 有一个由小写英文字母组成的字符串。她想让她的字符串变得“重复”。一个重复字符串的长度必须是偶数，且其前半部分与后半部分完全相同。例如，“lulu”、“abcabc”和“xx”是重复字符串，而“xyx”和“abac”则不是。

为了得到一个重复字符串，Lulu 可以从她的字符串中取出两个不重叠、非空的子串并将它们拼接在一起。这两个子串必须按照它们在原字符串中出现的先后顺序进行拼接。

她想知道，有多少种方法可以选择两个子串来构成一个重复字符串？如果 Lulu 使用的两个子串中至少有一个来自原字符串的不同位置，则视为两种不同的方法。

考虑字符串 “aaaa”。

• Lulu 有六种方法构成重复字符串 “aa”：通过将每个 “a” 与其后的每一个 “a” 匹配（1+2, 1+3, 1+4, 2+3, 2+4, 3+4）。
• 她还有三种方法构成 “aaaa”：“a”+“aaa”、“aa”+“aa” 和 “aaa”+“a”。

因此，Lulu 通过按顺序拼接 “aaaa” 中不重叠、非空的子串来构成重复字符串的方法共有九种。

输入格式

输入包含一行，为一个字符串 $s$ ($1 \le |s| \le 800, s \in \{a - z\}^*$)。这是 Lulu 的字符串。

输出格式

输出一个整数，表示 Lulu 通过按顺序拼接原字符串中两个不重叠、非空的子串来构成重复字符串的方法总数。

样例

样例输入 1

aaaa

样例输出 1

9

样例输入 2

axabxbcxcdxd

样例输出 2

22