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

Solution:
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Arrays;
import java.io.BufferedReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.io.InputStream;


public class VK2D {
        public static void main(String[] args) {
                InputStream inputStream = System.in;
                OutputStream outputStream = System.out;
                InputReader in = new InputReader(inputStream);
                PrintWriter out = new PrintWriter(outputStream);
                CodeVK2D solver = new CodeVK2D();
                solver.solve(1, in, out);
                out.close();
        }
}

class CodeVK2D
{
public void solve(int testNumber, InputReader in, PrintWriter out)
{
String s=in.next();
int l=s.length();
int pcount[]=new int[l];



boolean pal[][]=new boolean[l][l];
for(int i=0;i<l;i++)
{
Arrays.fill(pal[i],false);
}
fillPalindrome(s,pal);
long c=0;


pcount[0]=1;
for(int i=1;i<l;i++)
{
int a=pcount[i-1];
// int b=arr[j+1][j+i];
int count=0;
String st=s.substring(0,i+1);
for(int k=0;k<st.length();k++)
{
// String str=st.substring(0,k+2);
// if(isPalin(str))
{
// count++;
}
String str=st.substring(k);
if(pal[k][i])
{

if(k!=0)
{
c+=(long)pcount[k-1];
}
count++;
}
}
pcount[i]=a+count;
}









// for(int i=0;i<l;i++)
// {
// out.println(pcount[i]);
// }

out.println(c);
}



public void fillPalindrome(String s, boolean arr[][])
{
int l=s.length();
for(int i=0;i<l;i++)
{
arr[i][i]=true;
}
for(int i=0;i<l-1;i++)
{
if(s.charAt(i)==s.charAt(i+1))
{
arr[i][i+1]=true;
}
}
for(int i=2;i<l;i++)
{
for(int j=0;j<l-i;j++)
{
if(arr[j+1][j+i-1]&&s.charAt(j)==s.charAt(j+i))
{
arr[j][j+i]=true;
}
}
}


}

}









class InputReader {
    private BufferedReader reader;
    private StringTokenizer tokenizer;

    public InputReader(InputStream stream) {
        reader = new BufferedReader(new InputStreamReader(stream));
        tokenizer = null;
    }

    public String next() {
        while (tokenizer == null || !tokenizer.hasMoreTokens()) {
            try {
                tokenizer = new StringTokenizer(reader.readLine());
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }
        return tokenizer.nextToken();
    }

    public int nextInt() {
        return Integer.parseInt(next());
    }

    public long nextLong() {
        return Long.parseLong(next());
    }

    }