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 = 'import sys,math\nfrom sys import stdin,stdout\n\n\ns=stdin.readline().strip()\n\nispalin=[[0 for i in range(len(s)+1)] for i in range(len(s)+1)]\nsuff=[[-1 for i in range(len(s)+1)] for i in range(len(s)+1)]\npref=[[-1 for i in range(len(s)+1)] for i in range(len(s)+1)]\nlcp=[[0 for i in range(len(s)+1)] for i in range(len(s)+1)]\n\nfor i in range(0,len(s)):\n ispalin[i][i]=1;pref[i][i]=1;suff[i][i]=1\n ispalin[i][i+1]=1;pref[i][i+1]=2;suff[i][i+1]=2\n\n#for i in ispalin:\n #print(i)\n\nfor l in range(2,len(s)+1):\n for i in range(0,len(s)-l+1):\n  #print(i,i+l-1,s[i],s[i+l-1])\n  ispalin[i][i+l]=ispalin[i+1][i+l-1]*int(s[i]==s[i+l-1])\n  pref[i][i+l]=pref[i][i+l-1]+ispalin[i][i+l]\n  suff[i][i+l]=suff[i+1][i+l]+ispalin[i][i+l]\n\nfor i in range(len(s)):\n for j in range(i+1,len(s)):\n  lcp[i][j]=(lcp[i-1][j+1]+1)*int(s[i]==s[j])\n\n#\n\nans=0\n\nfor i in range(1,len(s)):\n for j in range(i,len(s)):\n  #if lcp[i-1][j]!=0:\n  #print(i,j,lcp[i-1][j],suff[i][j],pref[i][j],s[0:i],s[i:j],s[j:])\n  ans+=(lcp[i-1][j]*(suff[i][j]+pref[i][j]-1))\n#\nstdout.write(str(ans))\n\n\n'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 14307