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.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Application {

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String line = reader.readLine();

        List<int[]> palindromes = getPalindromes(line);
        int[] starts = getProjection(palindromes, 0);
        int[] ends = getProjection(palindromes, 1);
        Arrays.sort(starts);
        Arrays.sort(ends);

        int[] opened = new int[line.length()];
        int[] closed = new int[line.length()];

        int startPtr = 0, endPtr = 0, i = 0, open = 0, close = 0;
        while (startPtr < starts.length || endPtr < ends.length) {
            if (startPtr == starts.length || ends[endPtr] < starts[startPtr]) {
                while (i <= ends[endPtr]) {
                    opened[i] = open;
                    closed[i] = close;
                    i++;
                }
                close++;
                endPtr++;
            }
            else {
                while (i < starts[startPtr]) {
                    opened[i] = open;
                    closed[i] = close;
                    i++;
                }
                open++;
                startPtr++;
            }
        }

        while (i < line.length()) {
            opened[i] = open;
            closed[i] = close;
            i++;
        }

//        System.out.println("opened: " + Arrays.toString(opened));
//        System.out.println("closed: " + Arrays.toString(closed));
//        for (int[] palindrome : palindromes)
//            System.out.println(Arrays.toString(palindrome));

        long res = 0;

        for (int[] interval : palindromes) {
            int intersections = Math.min(
                opened[interval[0]] - closed[interval[0]],
                opened[interval[1]] - closed[interval[1]]
            ) + Math.max(
                opened[interval[1]] - opened[interval[0]],
                closed[interval[1]] - closed[interval[0]]
            );

            res += palindromes.size() - intersections;
        }

//        System.out.println(palindromes.size());
//        System.out.println();

        System.out.println(res / 2);
    }

    private static int[] getCounter(List<int[]> palindromes, int n) {
        int[] starts = getProjection(palindromes, 0);
        int[] ends = getProjection(palindromes, 1);
        int[] cntr = new int[n];

        Arrays.sort(starts);
        Arrays.sort(ends);

        int startPtr = 0, endPtr = 0, i = 0, cnt = 0;
        while (startPtr < starts.length || endPtr < ends.length) {
            if (startPtr == starts.length || ends[endPtr] < starts[startPtr]) {
                while (i <= ends[endPtr])
                    cntr[i++] = cnt;
                cnt--;
                endPtr++;
            }
            else {
                while (i < starts[startPtr])
                    cntr[i++] = cnt;
                cnt++;
                startPtr++;
            }
        }

        while (i < cntr.length)
            cntr[i++] = cnt;

        return cntr;
    }

    private static int[] getProjection(List<int[]> list, int idx) {
        int[] res = new int[list.size()];

        int i = 0;
        for (int[] e : list)
            res[i++] = e[idx];

        return res;
    }

    private static List<int[]> getPalindromes(String line) {
        List<int[]> res = new ArrayList<>();

        getPalindromes(line, 0, line.length() - 1, new Boolean[line.length()][line.length()], res);

        return res;
    }

    private static boolean getPalindromes(String line, int from, int to, Boolean[][] dp,  List<int[]> palindromes) {
        if (from > to)
            return true;

        if (dp[from][to] != null)
            return dp[from][to];

        boolean res = line.charAt(from) == line.charAt(to)
            && getPalindromes(line, from + 1, to - 1, dp, palindromes);

        getPalindromes(line, from + 1, to, dp, palindromes);
        getPalindromes(line, from, to - 1, dp, palindromes);

        if (res)
            palindromes.add(new int[]{from, to});

        dp[from][to] = res;
        return res;
    }
}