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 palSub(s,n,isPal):\n for gap in range(n):\n  for i in range(n-gap):\n   j = i + gap\n   if(gap == 0):\n    isPal[i][j] = 1\n   elif(gap == 1):\n    isPal[i][j] = 1 if(s[i] == s[j]) else 0\n   else:\n    isPal[i][j] = 1 if(s[i] == s[j] and isPal[i+1][j-1]) else 0\n return isPal\ndef case1(n,isPal,c1):\n for i in range(n):\n  for j in range(i,n):\n   if(i == j):\n    c1[i][j] = 1\n   else:\n    c1[i][j] = c1[i][j-1] + isPal[i][j]\n return c1\ndef case2(n,isPal,c2):\n for j in range(n-1,-1,-1):\n  for i in range(j,-1,-1):\n   if(i == j):\n    c2[i][j] = 1\n   else:\n    c2[i][j] = c2[i+1][j] + isPal[i][j]\n return c2\ndef getSub(s,n,c1,c2,res):\n for gap in range(n):\n  for i in range(n-gap):\n   j = i + gap\n   if(gap == 0):\n    res[i][j] = 0\n   elif(gap == 1):\n    res[i][j] = 1 if(s[i] == s[j]) else 0\n   elif(s[i] == s[j]):\n    res[i][j] = 1 + c1[i+1][j-1] + c2[i+1][j-1] + res[i+1][j-1]\n return res\ndef __starting_point():\n s = input()\n n = len(s)\n isPal = [[0 for x in range(n)]for y in range(n)]\n isPal = palSub(s,n,isPal)\n c1 = [[-1 for x in range(n)]for y in range(n)]\n c2 = [[-1 for x in range(n)]for y in range(n)]\n c1 = case1(n,isPal,c1)\n c2 = case2(n,isPal,c2)\n res = [[0 for x in range(n)]for y in range(n)]\n res = getSub(s,n,c1,c2,res)\n mycount = 0\n for i in range(n):\n  for j in range(n):\n   mycount += res[i][j]\n print(mycount)\n__starting_point()'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 14367