Problem: 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

Solution (in PYTHON3):

Solution:
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)