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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.LinkedList;
public class Main {


    /**
     * @param args
     * @throws IOException 
     */
    public static void main(String[] args) throws IOException {
        // TODO Auto-generated method stub
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out);
        char[] s=in.readLine().toCharArray();
        long f=System.currentTimeMillis();
        int[][] masCheck=new int[s.length][s.length];
        for(int i=0; i<s.length; i++) 
        {
            masCheck[i][i]=1;
        }
        for(int i=1; i<s.length; i++)
        {
            int j=i;
            int k=0;
            while(j<s.length)
            {
                //String cur=s.substring(k,j+1);
                //String rev=new StringBuffer(cur).reverse().toString();
                masCheck[j][k]=masCheck[j][k+1];
                int mid=(k+j+1)/2;
                int c=0;
                boolean check=true;
                for (int z=k; z<mid; z++)
                {
                    if (s[z]!=s[j-c]) {
                        check=false;
                        break;
                    }
                    c++;
                }
                if (check) masCheck[j][k]++;
                j++;
                k++;
            }
        }
        long count=0;
        
        /*for(int i=0; i<masCheck.length; i++)
        {
            for(int j=0; j<masCheck[i].length; j++)
            {
                out.print(masCheck[i][j]+" ");
            }
            out.println();
        }*/
                
        for(int i=0; i<masCheck.length-1; i++)
        {
            long curSum=0;
            for(int j=i+1; j<masCheck.length; j++)
                curSum+=masCheck[j][i+1];
            count+=curSum*masCheck[i][0];
        }
        /*for(int i=0; i<s.length(); i++)
        {
            for(int j=0; j<res[i].lens.size(); j++)
            {
                for (int z=i+res[i].lens.get(j); z<s.length(); z++)
                {
                    count+=res[z].lens.size();
                }
            }
        }*/
        out.println(count);
        out.close();
    }

}