You are given a string $S$. Find the number of ways to choose an unordered pair of non-overlapping non-empty substrings of this string (let's denote them by $s_1$ and $s_2$ in such a way that $s_2$ starts after $s_1$ ends) such that their concatenation $s_1 + s_2$ is a palindrome.
Two pairs $(s_1, s_2)$ and $(s_1', s_2')$ are different if $s_1$ is chosen at a different position from $s_1'$ or $s_2$ is chosen at a different position from $s_2'$.
-----Input-----
The first and only line of the input contains a single string $S$.
-----Output-----
Print a single line containing one integer — the number of ways to choose a valid pair of substrings.
-----Constraints-----
- $1 \le |S| \le 1,000$
- $S$ contains only lowercase English letters
-----Subtasks-----
Subtask #1 (25 points): $|S| \le 100$
Subtask #2 (75 points): original constraints
-----Example Input-----
abba
-----Example Output-----
7
-----Explanation-----
The following pairs of substrings can be chosen: ("a", "a"), ("a", "ba"), ("a", "bba"), ("ab", "a"), ("ab", "ba"), ("abb", "a"), ("b", "b").
import sys,math
from sys import stdin,stdout


s=stdin.readline().strip()

ispalin=[[0 for i in range(len(s)+1)] for i in range(len(s)+1)]
suff=[[-1 for i in range(len(s)+1)] for i in range(len(s)+1)]
pref=[[-1 for i in range(len(s)+1)] for i in range(len(s)+1)]
lcp=[[0 for i in range(len(s)+1)] for i in range(len(s)+1)]

for i in range(0,len(s)):
 ispalin[i][i]=1;pref[i][i]=1;suff[i][i]=1
 ispalin[i][i+1]=1;pref[i][i+1]=2;suff[i][i+1]=2

#for i in ispalin:
 #print(i)

for l in range(2,len(s)+1):
 for i in range(0,len(s)-l+1):
  #print(i,i+l-1,s[i],s[i+l-1])
  ispalin[i][i+l]=ispalin[i+1][i+l-1]*int(s[i]==s[i+l-1])
  pref[i][i+l]=pref[i][i+l-1]+ispalin[i][i+l]
  suff[i][i+l]=suff[i+1][i+l]+ispalin[i][i+l]

for i in range(len(s)):
 for j in range(i+1,len(s)):
  lcp[i][j]=(lcp[i-1][j+1]+1)*int(s[i]==s[j])

#

ans=0

for i in range(1,len(s)):
 for j in range(i,len(s)):
  #if lcp[i-1][j]!=0:
  #print(i,j,lcp[i-1][j],suff[i][j],pref[i][j],s[0:i],s[i:j],s[j:])
  ans+=(lcp[i-1][j]*(suff[i][j]+pref[i][j]-1))
#
stdout.write(str(ans))



import sys,math
from sys import stdin,stdout


s=stdin.readline().strip()

ispalin=[[0 for i in range(len(s)+1)] for i in range(len(s)+1)]
suff=[[-1 for i in range(len(s)+1)] for i in range(len(s)+1)]
pref=[[-1 for i in range(len(s)+1)] for i in range(len(s)+1)]
lcp=[[0 for i in range(len(s)+1)] for i in range(len(s)+1)]

for i in range(0,len(s)):
 ispalin[i][i]=1;pref[i][i]=1;suff[i][i]=1
 ispalin[i][i+1]=1;pref[i][i+1]=2;suff[i][i+1]=2

#for i in ispalin:
 #print(i)

for l in range(2,len(s)+1):
 for i in range(0,len(s)-l+1):
  #print(i,i+l-1,s[i],s[i+l-1])
  ispalin[i][i+l]=ispalin[i+1][i+l-1]*int(s[i]==s[i+l-1])
  pref[i][i+l]=pref[i][i+l-1]+ispalin[i][i+l]
  suff[i][i+l]=suff[i+1][i+l]+ispalin[i][i+l]

for i in range(len(s)):
 for j in range(i+1,len(s)):
  lcp[i][j]=(lcp[i-1][j+1]+1)*int(s[i]==s[j])

#

ans=0

for i in range(1,len(s)):
 for j in range(i,len(s)):
  #if lcp[i-1][j]!=0:
  #print(i,j,lcp[i-1][j],suff[i][j],pref[i][j],s[0:i],s[i:j],s[j:])
  ans+=(lcp[i-1][j]*(suff[i][j]+pref[i][j]-1))
#
stdout.write(str(ans))


