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.util.Scanner;


public class D {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        if (s.length() < 2) {
            System.out.println(0);
            return;
        }
        int n = s.length();
        long[]hash = new long[n], hash2 = new long[n];
        hash[0] = s.codePointAt(0)-96;
        hash2[n-1] = s.codePointAt(n-1)-96;
        long[]pow = new long[n];
        pow[0] = 1;
        for (int i = 1; i < n; i++) {
            pow[i] = pow[i-1]*31;
        }
        for (int i = 1; i < n; i++) {
            hash[i] = hash[i-1]+(s.codePointAt(i)-96)*pow[i];
        }
        for (int i = n-2; i >= 0; i--) {
            hash2[i] = hash2[i+1]+(s.codePointAt(i)-96)*pow[n-1-i];
        }
        long[]left = new long[n];
        for (int i = n-1; i > 0; i--) {
            left[i] = 1;
            for (int j = i+1; j < n; j++) {
                if ((hash[j]-hash[i-1])*pow[n-1-j]==(hash2[i]-(j < n-1 ? hash2[j+1] : 0))*pow[i]) {
                    left[i]++;
                }
            }
            if (i < n-1)
                left[i] += left[i+1];
        }
        long ans = left[1];
        for (int i = 1; i < n-1; i++) {
            long t = 1;
            for (int j = 0; j < i; j++) {
                if ((hash[i]-(j > 0 ? hash[j-1] : 0))*pow[n-1-i]==(hash2[j]-hash2[i+1])*pow[j]) {
                    t++;
                }
            }
            ans += t*left[i+1];
        }
        System.out.println(ans);
    }
}