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

public class p159D {
	public static void main(String[] args) {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		String s = null;

		try { s = new StringTokenizer(br.readLine()).nextToken(); } catch(Exception ex) {}

		boolean[][] pal = new boolean[s.length()][s.length()];
		for(int i=0; i<s.length()-1; ++i) {
			pal[i][i] = true;
			pal[i][i+1] = s.charAt(i) == s.charAt(i+1);
		}
		pal[s.length()-1][s.length()-1] = true;

		for(int i=2; i<s.length(); ++i)
			for(int j=0; i+j<s.length(); ++j)
				pal[j][i+j] = pal[j+1][i+j-1] && s.charAt(j) == s.charAt(i+j);


		int[] start = new int[s.length()], end = new int[s.length()];
		for(int i=0; i<s.length(); ++i) {
			for(int j=i+1; j<=s.length(); ++j) {
				if(pal[i][j-1]) {
				// if(s.substring(i, j).equals(new StringBuilder(s.substring(i, j)).reverse().toString())) {
					++start[i];
					++end[j-1];
				}
			}
		}

		for(int i=start.length-2; i>=0; --i) start[i] += start[i+1];

		long res = 0;
		for(int i=0; i<start.length-1; ++i) {
			res += end[i]*start[i+1];
		}

		System.out.println(res);
	}
}