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").

Difficulty: interview

Starter code:

Solutions:
def binarySearch(arr, l, r, x):
 mid=0
 while l <= r: 
  mid = l + (r - l)//2; 
  if arr[mid] == x: 
   return mid+1 
  elif arr[mid] < x: 
   l = mid + 1
  else: 
   r = mid - 1
 if mid!=len(arr):
  if arr[mid]<x:
   return mid+1
 return mid
s=input()
strt=[]
end=[]
plc=[]
landr=[]
l2r=[]
lr=[]
ans=0
n=len(s)
if n!=1:
 for i in range(n):
  strt.append([])
  end.append([])
  landr.append([0]*n)
  l2r.append([0]*n)
 for i in range(n):        
  for j in range(n):
   if i-j<0 or i+j>=n:
    break
   if (s[i-j]==s[i+j]):
    if i-j-1>=0:
     strt[i-j-1].append(2*j+1)
    if i+j+1<n:
     end[i+j+1].append(2*j+1)
   else:
    break
 for i in range(n):
  for j in range(n):
   if i-j<0 or i+j+1>=n:
    break
   if (s[i-j]==s[i+j+1]):
    if i-j-1>=0:
     strt[i-j-1].append(2*j+2)
    if i+j+2<n:
     end[i+j+2].append(2*j+2)
   else:
    break
 for i in range(n):
  end[i].sort()
  strt[i].sort()
 for i in range(n-1):
  for j in range(i+1,n):
   if s[i]==s[j]:
    lr.append([i,j])
    if i>0 and j<n-1:
     landr[i][j]=landr[i-1][j+1]+1
    else:
     landr[i][j]=1
 for i in lr:
  tempans=1
  l=i[0]
  r=i[1]
  length=r-l-1
  tempans+=binarySearch(strt[l],0,len(strt[l])-1,length)
  tempans+=binarySearch(end[r],0,len(end[r])-1,length)
  l2r[l][r]=tempans
 for i in range(n):
  for j in range(n):
   ans+=l2r[i][j]*landr[i][j]
print(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))




# cook your dish here
st = str(input())

def checkpal(i,j,k,l):
 
 a=i
 b=l
 while(a<b):
  if st[a] != st[b]:
   
   return -1
  
  if(a==j):
   a = k-1
  if(b==k):
   b = j+1

  a+=1
  b-=1 
 # print(i,j,k,l)
 # print("yes")
 return 1

l = len(st)
count = 0
for i in range(l):
 for j in range(i,l):
  for k in range(j+1,l):
   for m in range(k,l):
    if checkpal(i,j,k,m) == 1: 
     count += 1
   
print(count)

def palSub(s,n,isPal):
 for gap in range(n):
  for i in range(n-gap):
   j = i + gap
   if(gap == 0):
    isPal[i][j] = 1
   elif(gap == 1):
    isPal[i][j] = 1 if(s[i] == s[j]) else 0
   else:
    isPal[i][j] = 1 if(s[i] == s[j] and isPal[i+1][j-1]) else 0
 return isPal
def case1(n,isPal,c1):
 for i in range(n):
  for j in range(i,n):
   if(i == j):
    c1[i][j] = 1
   else:
    c1[i][j] = c1[i][j-1] + isPal[i][j]
 return c1
def case2(n,isPal,c2):
 for j in range(n-1,-1,-1):
  for i in range(j,-1,-1):
   if(i == j):
    c2[i][j] = 1
   else:
    c2[i][j] = c2[i+1][j] + isPal[i][j]
 return c2
def getSub(s,n,c1,c2,res):
 for gap in range(n):
  for i in range(n-gap):
   j = i + gap
   if(gap == 0):
    res[i][j] = 0
   elif(gap == 1):
    res[i][j] = 1 if(s[i] == s[j]) else 0
   elif(s[i] == s[j]):
    res[i][j] = 1 + c1[i+1][j-1] + c2[i+1][j-1] + res[i+1][j-1]
 return res
def __starting_point():
 s = input()
 n = len(s)
 isPal = [[0 for x in range(n)]for y in range(n)]
 isPal = palSub(s,n,isPal)
 c1 = [[-1 for x in range(n)]for y in range(n)]
 c2 = [[-1 for x in range(n)]for y in range(n)]
 c1 = case1(n,isPal,c1)
 c2 = case2(n,isPal,c2)
 res = [[0 for x in range(n)]for y in range(n)]
 res = getSub(s,n,c1,c2,res)
 mycount = 0
 for i in range(n):
  for j in range(n):
   mycount += res[i][j]
 print(mycount)
__starting_point()