P16078 [ICPC 2023 NAC] Repetitive String Invention

露露有一个由小写英文字母组成的字符串。她想让自己的字符串变成 **重复字符串**。重复字符串的长度为偶数，并且字符串的前一半与后一半完全相同。例如，“lulu”、“abcabc” 和 “xx” 是重复字符串，而 “xyx” 和 “abac” 则不是。 为了得到重复字符串，露露可以从她的字符串中选取两个不重叠、非空的子串，并将它们按顺序拼接起来。这两个子串必须按照它们在原字符串中出现的顺序进行拼接。 她想知道，有多少种选择两个子串的方式可以构成一个重复字符串？如果至少有一个子串来自原字符串的不同位置，则认为两种选择方式不同。 考虑字符串 “aaaa”。 - 有 6 种方式构成重复字符串 “aa”：将每个 “a” 与它后面的每个 “a” 配对（1+2, 1+3, 1+4, 2+3, 2+4, 3+4）。 - 还有 3 种方式构成重复字符串 “aaaa”：“a”+“aaa”、“aa”+“aa” 和 “aaa”+“a”。 因此，通过从 “aaaa” 中按顺序拼接两个不重叠、非空的子串，露露一共有 9 种方式构成重复字符串。

输入只有一行，包含一个字符串 $ s $（$ 1 \le |s| \le 800 $，$ s $ 由小写字母组成）。这是露露的字符串。

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

翻译由 DeepSeek V3.2 完成