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

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = 'def binarySearch(arr, l, r, x):\n mid=0\n while l <= r: \n  mid = l + (r - l)//2; \n  if arr[mid] == x: \n   return mid+1 \n  elif arr[mid] < x: \n   l = mid + 1\n  else: \n   r = mid - 1\n if mid!=len(arr):\n  if arr[mid]<x:\n   return mid+1\n return mid\ns=input()\nstrt=[]\nend=[]\nplc=[]\nlandr=[]\nl2r=[]\nlr=[]\nans=0\nn=len(s)\nif n!=1:\n for i in range(n):\n  strt.append([])\n  end.append([])\n  landr.append([0]*n)\n  l2r.append([0]*n)\n for i in range(n):        \n  for j in range(n):\n   if i-j<0 or i+j>=n:\n    break\n   if (s[i-j]==s[i+j]):\n    if i-j-1>=0:\n     strt[i-j-1].append(2*j+1)\n    if i+j+1<n:\n     end[i+j+1].append(2*j+1)\n   else:\n    break\n for i in range(n):\n  for j in range(n):\n   if i-j<0 or i+j+1>=n:\n    break\n   if (s[i-j]==s[i+j+1]):\n    if i-j-1>=0:\n     strt[i-j-1].append(2*j+2)\n    if i+j+2<n:\n     end[i+j+2].append(2*j+2)\n   else:\n    break\n for i in range(n):\n  end[i].sort()\n  strt[i].sort()\n for i in range(n-1):\n  for j in range(i+1,n):\n   if s[i]==s[j]:\n    lr.append([i,j])\n    if i>0 and j<n-1:\n     landr[i][j]=landr[i-1][j+1]+1\n    else:\n     landr[i][j]=1\n for i in lr:\n  tempans=1\n  l=i[0]\n  r=i[1]\n  length=r-l-1\n  tempans+=binarySearch(strt[l],0,len(strt[l])-1,length)\n  tempans+=binarySearch(end[r],0,len(end[r])-1,length)\n  l2r[l][r]=tempans\n for i in range(n):\n  for j in range(n):\n   ans+=l2r[i][j]*landr[i][j]\nprint(ans)'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 14713