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.PrintStream;
import java.util.StringTokenizer;
import java.util.logging.Level;
import java.util.logging.Logger;

public class ProblemD {

    private final BufferedReader in;
    private final PrintStream out;
    private StringTokenizer tok = new StringTokenizer("");
    private String nextLine = null;

    public static void main(String[] args) throws Exception {
        new ProblemD();
    }

    private ProblemD() throws Exception {
        in = new BufferedReader(new InputStreamReader(System.in));
        out = System.out;
        start();
        end();
    }

    private int nextInt() {
        return Integer.parseInt(nextWord());
    }

    private String nextWord() {
        if (tok.hasMoreTokens()) {
            return tok.nextToken();
        } else {
            while (!tok.hasMoreTokens()) {
                try {
                    nextLine = in.readLine();
                    if (nextLine == null) {
                        return null;
                    } else {
                        tok = new StringTokenizer(nextLine);
                    }
                } catch (IOException ex) {
                    Logger.getLogger(ProblemD.class.getName()).log(Level.SEVERE, null, ex);
                }
            }
            return tok.nextToken();
        }
    }
    long[] hashTo;
    long[] hashFromRev;
    long p = 1000000007;
    long[] pow = new long[2012];
    int n;

    private void start() {
        String s = nextWord();
        n = s.length();
        hashFromRev = new long[n + 2];
        hashTo = new long[n + 2];
        for (int i = 1; i <= n; i++) {
            hashTo[i] = hashTo[i - 1] * p + s.charAt(i - 1);
        }
        for (int i = n; i >= 1; i--) {
            hashFromRev[i] = hashFromRev[i + 1] * p + s.charAt(i - 1);
        }
        pow[0] = 1;
        for (int i = 1; i < pow.length; i++) {
            pow[i] = pow[i - 1] * p;
        }

        long[] polyUpTo = new long[n + 2];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                if (getHash(j, i) == getRevHash(j, i)) {
                    polyUpTo[i]++;
                }
            }
        }
        long[] polyFrom = new long[n + 2];
        for (int i = n; i >= 1; i--) {
            polyFrom[i] = polyFrom[i + 1];
            for (int j = i; j <= n; j++) {
                if (getHash(i, j) == getRevHash(i, j)) {
                    polyFrom[i]++;
                }
            }
        }
//        for (int i = 1; i <= n; i++) {
//            out.print(polyUpTo[i]);
//        }
//        out.println();
//        for (int i = 1; i <= n; i++) {
//            out.print(polyFrom[i]);
//        }
//        out.println();
        long res = 0;
        for (int i = 1; i <= n; i++) {
            res += polyUpTo[i] * polyFrom[i + 1];
        }
        out.println(res);
    }

    long getHash(int l, int r) {
        return hashTo[r] - hashTo[l - 1] * pow[r - l + 1];
    }

    long getRevHash(int l, int r) {
        return hashFromRev[l] - hashFromRev[r + 1] * pow[r - l + 1];
    }

    private void end() {
        out.close();
    }
}