给你一个由小写字母组成的非空字符串 s 。求该字符串的非重叠回文子串对的数量。
以更正式的方式,您必须找到元组 (a, b, x, y) 的数量,使得 1 ≤ a ≤ b < x ≤ y ≤ |s|子串 s[a...b]、s[x...y] 是回文。
回文是一个可以从左到右和从右到左以相同方式读取的字符串。例如,“abacaba”、“z”、“abba”是回文。
字符串 s = s1s2... s|s| 的子串 s[i... j] (1 ≤ i ≤ j ≤ |s|)是一个字符串 sisi + 1... sj。例如,字符串 s = "abacaba" 的子字符串 s[2...4] 等于 "bac"。
输入
第一行输入包含一个由小写字母('a'...'z')组成的非空字符串 s,s 最多包含 2000 个字符。
输出
输出一个数字 — s 的非重叠回文子串对的数量。
请不要使用 %lld 格式说明符在 С++ 中读取或写入 64 位整数。最好使用 cin、cout 流或 %I64d 格式说明符。
示例
输入 #1
aa
输出 #1
1
输入 #2
aaa
输出 #2
5
输入 #3
abacaba
输出 #3
36