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 Solution {
    private static long [][] count;
    private static String str;
    private static int [][] poly;
    private static int [] z;
    private static String string;
    private static void zFunction(String s) {        
        int  i;
        int n = s.length();
        z[0] = n;
        int l = 0;
        int r = 0;
        for (i = 1; i < n; i++) {
            z[i] = 0;
            if ((i >= l) && (i < r)) {
                z[i] = Math.min(z[i - l], r - i);
            }
            while ((i + z[i] < n) && (s.charAt(z[i]) == s.charAt(i + z[i]))) {
                z[i]++;
            }
            if (i + z[i] > r) {
                l = i;
                r = i + z[i];
            }
        }
    }
    private static int isPolyndrom(int left, int rigth) {
        int i;
        for (i = left; i <= (left + rigth) / 2; i++) {
            if (str.charAt(i) != str.charAt(rigth - i + left)) {
                return 0;
            }
        }
        return 1;
    }
    private static long howMany(int left, int rigth) {
        if (left > rigth) {
            return 0;
        }
        if (count[left][rigth] != -1) {
            return count[left][rigth];
        }        
        if (left == rigth) {
            count[left][rigth] = 1; 
            return count[left][rigth];
        }
        count[left][rigth] = howMany(left, rigth - 1) + howMany(left + 1, rigth) - howMany(left + 1, rigth - 1) + poly[left][rigth];
        return count[left][rigth];
    }
    
    public static void main(String [] args) {
        Scanner scan = new Scanner(System.in);
        str = scan.nextLine();
        count = new long [str.length()][str.length()];
        int i;
        int j;
        string = str;
        for (i = str.length() - 1; i > -1; i--) {
            string += str.charAt(i);
        }
        z = new int [str.length() * 2 + 10];
        poly = new int [str.length()][str.length()];
        for (i = 0; i < str.length(); i++) {
            int p = str.length() - i;
            zFunction(string);
            for (j = p; j < string.length(); j++) {
                if (z[j] == string.length() - j) {
                    poly[i][i + z[j] - 1] = 1;
                }
            }
            string = string.substring(0, string.length() - 1);
            string = string.substring(1);           
        }        
        for (i = 0; i < str.length(); i++) {
            for (j = i; j < str.length(); j++) {
                count[i][j] = -1;
            }
        }        
        howMany(0, str.length() - 1);
        long ans = 0;
        for (i = 0; i < str.length(); i++) {
            for (j = i; j < str.length(); j++) {
                ans += poly[i][j] * howMany(0, i - 1);
            }
        }
        System.out.println(ans);
        
    }
}