题目描述

给定一个由小写字母组成的非空字符串 $s$。求该字符串中互不重叠的回文子串对的个数。

更严格地说，你需要求出满足 $1 \le a \le b \lt x \le y \le |s|$ 且子串 $s[a \ldots b]$、$s[x \ldots y]$ 都是回文串的四元组 $(a, b, x, y)$ 的数量。

回文串是指从左往右读和从右往左读都相同的字符串。例如 "abacaba"、"z"、"abba" 都是回文串。

字符串 $s = s_1 s_2 \ldots s_{|s|}$ 的子串 $s[i \ldots j]$（$1 \le i \le j \le |s|$）是指 $s_i s_{i+1} \ldots s_j$。例如 "abacaba" 的子串 $s[2 \ldots 4]$ 是 "bac"。

输入格式

输入的第一行包含一个由小写字母（'a'…'z'）组成的非空字符串 $s$，长度不超过 2000。

输出格式

输出一个数——$s$ 中互不重叠的回文子串对的个数。

aa

1

aaa

5

abacaba

36