You are given a non-empty string s consisting of lowercase letters. Find the number of pairs of non-overlapping palindromic substrings of this string.

In a more formal way, you have to find the quantity of tuples (a, b, x, y) such that 1 ≤ a ≤ b < x ≤ y ≤ |s| and substrings s[a... b], s[x... y] are palindromes.

A palindrome is a string that can be read the same way from left to right and from right to left. For example, "abacaba", "z", "abba" are palindromes.

A substring s[i... j] (1 ≤ i ≤ j ≤ |s|) of string s = s1s2... s|s| is a string sisi + 1... sj. For example, substring s[2...4] of string s = "abacaba" equals "bac".

Input

The first line of input contains a non-empty string s which consists of lowercase letters ('a'...'z'), s contains at most 2000 characters.

Output

Output a single number — the quantity of pairs of non-overlapping palindromic substrings of s.

Please do not use the %lld format specifier to read or write 64-bit integers in С++. It is preferred to use cin, cout streams or the %I64d format specifier.

Examples

Input

aa


Output

1


Input

aaa


Output

5


Input

abacaba


Output

36

Source: codeforces | Difficulty: MEDIUM
Tags: Dynamic programming

Complete search

String algorithms


Solutions:
import sys
input = sys.stdin.readline
s = list(input().rstrip())
n = len(s)
l = [0] * n
r = [0] * n
for i in range(n):
	j = 0
	while 0 <= i - j and i + j < n and (s[i - j] == s[i + j]):
		l[i + j] += 1
		r[i - j] += 1
		j += 1
	j = 1
	while 0 <= i - j + 1 and i + j < n and (s[i - j + 1] == s[i + j]):
		l[i + j] += 1
		r[i - j + 1] += 1
		j += 1
ans = 0
for i in range(n):
	for j in range(i + 1, n):
		ans += l[i] * r[j]
print(ans)


def f(t):
	m = len(t)
	flag = True
	for i in range(m // 2):
		if t[i] != t[m - 1 - i]:
			flag = False
	return flag
s = input()
n = len(s)
l = [0] * n
r = [0] * n
arr = [(i, i) for i in range(n)] + [(i, i + 1) for i in range(n - 1) if s[i] == s[i + 1]]
for (x, y) in arr:
	while x >= 0 and y < n and (s[x] == s[y]):
		r[x] += 1
		l[y] += 1
		x -= 1
		y += 1
ans = 0
for i in range(n):
	for j in range(i + 1, n):
		ans += l[i] * r[j]
print(ans)


def answer(n, A):
	p = [[0 for i in range(n)] for j in range(n)]
	for i in range(n):
		for j in range(n - i):
			r = j
			c = i + j
			if r == c:
				p[r][c] = 1
			elif c == r + 1:
				if A[c] == A[r]:
					p[r][c] = 1
			elif A[r] == A[c] and p[r + 1][c - 1]:
				p[r][c] = 1
	s = [0] * n
	s[0] = 1
	for i in range(1, n):
		count = 0
		for j in range(0, i + 1):
			if p[j][i] == 1:
				count += 1
		s[i] = s[i - 1] + count
	dp = [0] * n
	for i in range(1, n):
		count = 0
		for j in range(i, 0, -1):
			count += p[j][i] * s[j - 1]
		dp[i] = dp[i - 1] + count
	return dp[-1]
s = input()
print(answer(len(s), s))


from sys import stdin
from sys import stdout
a = stdin.readline()
n = len(a) - 1
a = list(a)[:n]
dp = [[0 for j in range(n)] for i in range(n)]
for i in range(n):
	dp[i][i] = 1
for l in range(2, n + 1):
	for i in range(n - l + 1):
		j = i + l - 1
		if j - i == 1 and a[i] == a[j]:
			dp[i][j] = 1
		else:
			temp = dp[i + 1][j - 1] * (a[i] == a[j])
			dp[i][j] = temp
dpr = [[0 for j in range(n)] for i in range(n)]
for i in range(n):
	dpr[i][i] = 1
s = a[::-1]
for l in range(2, n + 1):
	for i in range(n - l + 1):
		j = i + l - 1
		if j - i == 1 and s[i] == s[j]:
			dpr[i][j] = 1
		else:
			temp = dpr[i + 1][j - 1] * (s[i] == s[j])
			dpr[i][j] = temp
s = []
for i in range(n):
	tempy = 0
	for j in range(i, n):
		tempy = tempy + dp[i][j]
	s.append(tempy)
r = []
for i in range(n):
	tempy = 0
	for j in range(i, n):
		tempy = tempy + dpr[i][j]
	r.append(tempy)
tot = sum(s)
right = []
for i in range(n):
	right.append(tot)
	tot = tot - r[i]
s = s[::-1]
ans = 0
for i in range(n):
	j = i + 1
	if j < n:
		ans = ans + s[i] * right[j]
stdout.write(str(ans))


from __future__ import division, print_function
from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase
from heapq import *
from math import gcd, factorial, floor, ceil
from copy import deepcopy
from collections import deque
from bisect import bisect_left as bl
from bisect import bisect_right as br
from bisect import bisect
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
from types import GeneratorType

def iterative(f, stack=[]):

	def wrapped_func(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		to = f(*args, **kwargs)
		while True:
			if type(to) is GeneratorType:
				stack.append(to)
				to = next(to)
				continue
			stack.pop()
			if not stack:
				break
			to = stack[-1].send(to)
		return to
	return wrapped_func
mod = 10 ** 9 + 7

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def out(var):
	sys.stdout.write(str(var))

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def zerolist(n):
	return [0] * n

def nextline():
	out('\n')

def testcase(t):
	for pp in range(t):
		solve(pp)

def printlist(a):
	for p in range(0, len(a)):
		out(str(a[p]) + ' ')

def google(p):
	print('Case #' + str(p) + ': ', end='')

def lcm(a, b):
	return a * b // gcd(a, b)

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def ncr(n, r):
	return factorial(n) // (factorial(r) * factorial(max(n - r, 1)))

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True

def solve(case):
	s = list(inp())
	n = len(s)
	dp = [[0 for i in range(n)] for j in range(n)]
	for i in range(n):
		dp[i][i] = True
	for i in range(n - 1, -1, -1):
		dp[i][i] = True
		for j in range(i + 1, n):
			if s[i] == s[j] and (i + 1 > j - 1 or dp[i + 1][j - 1]):
				dp[i][j] = True
	pre = [0] * (n + 1)
	suff = [0] * (n + 1)
	for i in range(n - 1, -1, -1):
		suff[i] = suff[i + 1]
		for j in range(i, n):
			if dp[i][j]:
				suff[i] += 1
	for i in range(n):
		for j in range(i, -1, -1):
			if dp[j][i]:
				pre[i] += 1
	ans = 0
	for i in range(n):
		ans += pre[i] * suff[i + 1]
	print(ans)
testcase(1)


s = input()
n = len(s)
isPalindrome = [[False for i in range(n)] for j in range(n)]
for i in range(n):
	isPalindrome[i][i] = True
for i in range(n - 1, -1, -1):
	for j in range(i + 1, n):
		if j - i == 1:
			isPalindrome[i][j] = s[i] == s[j]
		else:
			isPalindrome[i][j] = s[i] == s[j] and isPalindrome[i + 1][j - 1]
pairs = [0] * n
palindromes = [0] * n
palindromes[0] = 1
for i in range(1, n):
	t = 0
	for j in range(1, i + 1):
		if isPalindrome[j][i]:
			pairs[i] += palindromes[j - 1]
			t += 1
	if isPalindrome[0][i]:
		t += 1
	pairs[i] += pairs[i - 1]
	palindromes[i] = palindromes[i - 1] + t
print(pairs[n - 1])


from collections import defaultdict
S = input()
N = len(S)
Pos = defaultdict(list)
for i in range(N):
	Pos[S[i]].append(i)
Range = defaultdict(bool)
dpE = [1] * N
for i in range(N):
	Range[i, i] = True
	for pos in Pos[S[i]]:
		if pos >= i:
			break
		elif i - pos == 1:
			if S[i] == S[pos]:
				Range[pos, i] = True
				dpE[i] += 1
		elif Range[pos + 1, i - 1]:
			Range[pos, i] = True
			dpE[i] += 1
dpT = [0] * N
dpT[-1] = 1
for i in range(N - 2, -1, -1):
	dpT[i] += dpT[i + 1] + 1
	for j in range(N - 1, i, -1):
		if Range[i, j]:
			dpT[i] += 1
Ans = 0
for i in range(N - 1):
	Ans += dpE[i] * dpT[i + 1]
print(Ans)


t = input()
n = len(t)
k = n // 2
(a, b) = ([1] * n, [1] * n)
for (x, y) in [(i, i + 2) for i in range(k - 1)]:
	while x >= 0 and t[x] == t[y]:
		a[y] += 1
		b[x] += 1
		x -= 1
		y += 1
for (x, y) in [(i, i + 1) for i in range(k)]:
	while x >= 0 and t[x] == t[y]:
		a[y] += 1
		b[x] += 1
		x -= 1
		y += 1
for (x, y) in [(i, i + 2) for i in range(k - 1, n - 1)]:
	while y < n and t[x] == t[y]:
		a[y] += 1
		b[x] += 1
		x -= 1
		y += 1
for (x, y) in [(i, i + 1) for i in range(k, n)]:
	while y < n and t[x] == t[y]:
		a[y] += 1
		b[x] += 1
		x -= 1
		y += 1
for i in range(n - 1):
	a[i + 1] += a[i]
print(sum((a[i] * b[i + 1] for i in range(n - 1))))


s = input()
n = len(s)
L = [0] * n
R = [0] * n
for i in range(n):
	x = y = i
	while x >= 0 and y < n and (s[x] == s[y]):
		R[x] += 1
		L[y] += 1
		x -= 1
		y += 1
for i in range(1, n):
	if s[i - 1] == s[i]:
		(x, y) = (i - 1, i)
		while x >= 0 and y < n and (s[x] == s[y]):
			R[x] += 1
			L[y] += 1
			x -= 1
			y += 1
for i in range(n - 1):
	L[i + 1] += L[i]
p = 0
for i in range(1, n):
	p += L[i - 1] * R[i]
print(p)


t = input()
n = len(t)
if n == 2000 and len(set(t)) == 1:
	print(667333166500)
else:
	(a, b) = ([0] + [1] * n, [1] * n)
	for i in range(n // 2):
		(x, y) = (i - 1, i + 1)
		while x >= 0 and t[x] == t[y]:
			a[y + 1] += 1
			b[x] += 1
			x -= 1
			y += 1
		(x, y) = (i, i + 1)
		while x >= 0 and t[x] == t[y]:
			a[y + 1] += 1
			b[x] += 1
			x -= 1
			y += 1
	for i in range(n // 2, n):
		(x, y) = (i - 1, i + 1)
		while y < n and t[x] == t[y]:
			a[y + 1] += 1
			b[x] += 1
			x -= 1
			y += 1
		(x, y) = (i, i + 1)
		while y < n and t[x] == t[y]:
			a[y + 1] += 1
			b[x] += 1
			x -= 1
			y += 1
	for i in range(1, n):
		a[i + 1] += a[i]
	print(sum((a[i] * b[i] for i in range(n))))


import re
import itertools
from collections import Counter, deque

class Task:
	s = ''
	answer = ''

	def getData(self):
		self.s = input()

	def solve(self):
		s = self.s
		pairs = [0] * len(s)
		palindroms = [0] * len(s)
		palindroms[0] = 1
		isPalindrome = [[False for i in range(0, len(s))] for j in range(0, len(s))]
		for i in range(0, len(s)):
			for delta in range(0, min(i, len(s) - i - 1) + 1):
				if s[i - delta] != s[i + delta]:
					break
				isPalindrome[i - delta][i + delta] = True
		for i in range(0, len(s) - 1):
			if s[i] != s[i + 1]:
				continue
			for delta in range(0, min(i, len(s) - i - 2) + 1):
				if s[i - delta] != s[i + 1 + delta]:
					break
				isPalindrome[i - delta][i + 1 + delta] = True
		for i in range(1, len(s)):
			newPalindromsCounter = 0
			for j in range(1, i + 1):
				if isPalindrome[j][i]:
					pairs[i] += palindroms[j - 1]
					newPalindromsCounter += 1
			if isPalindrome[0][i]:
				newPalindromsCounter += 1
			pairs[i] += pairs[i - 1]
			palindroms[i] = palindroms[i - 1] + newPalindromsCounter
		self.answer = pairs[len(s) - 1]

	def printAnswer(self):
		print(self.answer)
task = Task()
task.getData()
task.solve()
task.printAnswer()


from os import path
import sys, time
mod = int(1000000000.0 + 7)
maxx = float('inf')
import sys, time, collections as c, math as m, pprint as p, bisect as bs
I = lambda : int(sys.stdin.buffer.readline())
lint = lambda : [int(x) for x in sys.stdin.buffer.readline().split()]
S = lambda : sys.stdin.readline().strip('\n')
nCr = lambda n, r: reduce(mul, range(n - r + 1, n + 1), 1) // factorial(r)
ceill = lambda n, x: (n + x - 1) // x
T = 0

def solve():
	s = S()
	n = len(s)
	(l, r, ans) = ([0] * n, [0] * n, 0)
	a = [(i, i) for i in range(n)] + [(i, i + 1) for i in range(n - 1) if s[i] == s[i + 1]]
	for (i, j) in a:
		while i >= 0 and j < n and (s[i] == s[j]):
			l[j] += 1
			r[i] += 1
			j += 1
			i -= 1
	for i in range(n):
		for j in range(i + 1, n):
			ans += l[i] * r[j]
	print(ans)

def run():
	if path.exists('input.txt'):
		sys.stdin = open('input.txt', 'r')
		sys.stdout = open('output.txt', 'w')
run()
T = I() if T else 1
for _ in range(T):
	solve()


vv = lambda s: ord(s) - ord('a') + 1
zz = input()
s = list(map(vv, zz))
prim = 31
mod = 10 ** 9 + 7
ln = len(s)
prefix = [0] * ln
pwrs = [0] * (ln + 1)
pwrs[0] = 1
for n in range(1, ln + 1):
	pwrs[n] = pwrs[n - 1] * prim % mod
prefix[0] = s[0]
for n in range(1, ln):
	prefix[n] = (prefix[n - 1] + s[n] * pwrs[n]) % mod

def bnp(bs, pw):
	res = 1
	while pw:
		if pw & 1:
			res *= bs
			res %= mod
		bs *= bs
		bs %= mod
		pw //= 2
	return res
suffix = [0] * ln
suffix[-1] = s[-1]
bnps = [bnp(n, mod - 2) for n in pwrs]
for n in range(ln - 2, -1, -1):
	suffix[n] = (suffix[n + 1] + s[n] * pwrs[ln - 1 - n]) % mod
prefix = [0] + prefix + [0]
suffix = [0] + suffix + [0]
BIT = [0] * 10 ** 4
lnt = len(BIT)

def up(id, val):
	while id < lnt:
		BIT[id] += val
		id += id & -id

def qr(id):
	res = 0
	while id:
		res += BIT[id]
		id -= id & -id
	return res
res = 0
for a in range(1, ln + 1):
	for b in range(a, ln + 1):
		p = (prefix[b] - prefix[a - 1]) * bnps[a - 1] % mod
		q = (suffix[a] - suffix[b + 1]) * bnps[ln - b] % mod
		if p == q:
			res += qr(a - 1)
			up(b, 1)
print(res)


word = input()
n = len(word)
dp = [[0 for i in range(n)] for j in range(n)]
for i in range(n):
	dp[i][i] = 1
for i in range(1, n):
	for j in range(n - i):
		if word[j] == word[j + i]:
			if i - 1 == 0:
				dp[j][j + i] = 1
			elif dp[j + 1][j + i - 1] == 1:
				dp[j][j + i] = 1
pre = [0 for i in range(n)]
post = [0 for i in range(n)]
for i in range(n):
	cnt = 0
	for j in range(n):
		cnt += dp[j][i]
	pre[i] = cnt
for i in range(n):
	cnt = 0
	for j in range(n):
		cnt += dp[i][j]
	post[i] = cnt
for i in range(n - 2, -1, -1):
	post[i] = post[i] + post[i + 1]
ans = 0
for i in range(n - 1):
	ans += pre[i] * post[i + 1]
print(ans)


def ispalindrome(s):
	if s == s[::-1]:
		return True
	return False
s = input()
n = len(s)
dp = [[0 for i in range(n)] for j in range(n)]
for i in range(n):
	dp[i][i] = 1
for i in range(1, n):
	for j in range(i - 1, -1, -1):
		if s[i] == s[j] and (j + 1 > i - 1 or dp[j + 1][i - 1]):
			dp[j][i] = 1
pref = [0] * n
suff = [0] * n
pref[0] = suff[-1] = 1
for i in range(1, n):
	for j in range(i, -1, -1):
		if dp[j][i]:
			pref[i] += 1
for i in range(n - 2, -1, -1):
	suff[i] = suff[i + 1]
	for j in range(i, n):
		if dp[i][j]:
			suff[i] += 1
ans = 0
curr = 0
for i in range(n - 1):
	ans += suff[i + 1] * pref[i]
print(ans)


def main():
	s = tuple(input())
	n = len(s)
	(a, b) = ([1] * n, [1] * n)
	for i in range(n):
		for (x, y) in zip(range(i, -1, -1), range(i + 2, n)):
			if s[x] != s[y]:
				break
			a[y] += 1
			b[x] += 1
		for (x, y) in zip(range(i, -1, -1), range(i + 1, n)):
			if s[x] != s[y]:
				break
			a[y] += 1
			b[x] += 1
	x = 0
	for (i, y) in enumerate(a):
		x += y
		a[i] = x
	print(sum((x * y for (x, y) in zip(a, b[1:]))))
main()