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

public class CF159D {
	boolean[][] isPalin;
	void findPalindromes(char[] s) {
		int n = s.length;
		isPalin = new boolean[n][n];
		for(int i = 0 ; i < n ; i++)
			isPalin[i][i] = true;
		for(int i = 0 ; i < n - 1 ; i++)
			isPalin[i][i + 1] = s[i] == s[i + 1];
		for(int len = 2 ; len < n ; len++) {
			for(int i = 0 ; i < n - len ; i++) {
				int j = i + len;
				if(s[i] == s[j] && isPalin[i + 1][j - 1])
					isPalin[i][j] = true;
			}
		}
	}
	public CF159D() {
		FS scan = new FS();
		char[] s = scan.next().toCharArray();
		findPalindromes(s);
		int n = s.length;
		int[] sum = new int[n];
		for(int i = 0 ; i < n ; i++)
			for(int j = i ; j < n ; j++)
				if(isPalin[i][j])
					sum[i]++;
		for(int i = 1 ; i < n ; i++)
			sum[i] += sum[i - 1];
		long res = 0;
		for(int i = 0 ; i < n ; i++)
			for(int j = i ; j < n ; j++)
				if(isPalin[i][j])
					res += sum[n - 1] - sum[j];
		System.out.println(res);
	}
	class FS {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer("");
		public String next() {
			while(!st.hasMoreTokens()) {
				try { st = new StringTokenizer(br.readLine()); }
				catch(Exception e) { e.printStackTrace(); }
			}
			return st.nextToken();
		}
	}
	public static void main(String[] args) { new CF159D(); }
}