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.*;
import java.util.*;

public class cc3 {

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new
                    InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

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

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

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }

    static class num{
        int a , b;
        num(int a , int b){
            this.a = a;
            this.b = b;
        }
    }
    static int GetRightPosition(ArrayList<num> ar, int l, int r, int key)
    {
        int m;

        while( r - l > 1 )
        {
            m = l + (r - l)/2;

            if( ar.get(m).a <= key )
                l = m;
            else
                r = m;
        }

        return l;
    }

    public static void main(String[] args) {
        FastReader fr = new FastReader();
        String s = fr.next();
        boolean palin[][] = new boolean[s.length()][s.length()];
        for(int i=0;i<s.length();++i){
            for(int j=0;j<s.length();++j){
                if(i == j){
                    palin[i][j] = true;
                }
                else {
                    if (Math.abs(j - i) == 1 && s.charAt(i) == s.charAt(j)) {
                        palin[i][j] = true;
                        palin[j][i] = true;
                    } else {
                        if (s.charAt(i) == s.charAt(j)) {
                            if(i<j){
                                if(palin[i+1][j-1]){
                                    palin[i][j] = true;
                                }
                            }
                            else{
                                if(palin[j+1][i-1]){
                                    palin[j][i] = true;
                                }
                            }
                        }
                    }
                }
            }
        }
        ArrayList<num> ar = new ArrayList<num>();
        for(int i=0;i<s.length();++i){
            for(int j=i;j<s.length();++j){
                if(palin[i][j]){
                    ar.add(new num(Math.min(i,j),Math.max(i,j)));
                }
            }
        }
        ar.sort(new Comparator<num>() {
            @Override
            public int compare(num o1, num o2) {
                if(o1.a < o2.a)
                    return -1;
                if(o1.a == o2.a)
                    return 0;
                return 1;
            }
        });
        long res = 0;
        /*for(int i=0;i<ar.size();++i){
            System.out.println(ar.get(i).a+" "+ar.get(i).b);
        }
        System.out.println();*/
        for(int i=0;i<ar.size();++i){
            long extreme = GetRightPosition(ar , 0 , ar.size() , ar.get(i).b) + 1;
            //System.out.println(ar.size()+" "+ (extreme) + " val "+(ar.size()-extreme));
            res += ar.size()-extreme;
        }
        System.out.println(res);
    }
}