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;

public class pairs {
	static long[] potencias;
	static long[] hashing;
	static long[] ihashing;
	static int largo;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String s = br.readLine();
		largo = s.length();
		int b = 33;
		potencias = new long[largo];
		potencias[0]=1;
		hashing = new long[largo];
		ihashing = new long[largo];
		for(int i =1;i<largo;i++) potencias[i]=potencias[i-1]*b;
		hashing[largo-1]=s.charAt(largo-1);
		ihashing[0]=s.charAt(0);
		for(int i=largo-2;i>=0;i--){
			ihashing[largo-1-i]=ihashing[largo-2-i]*b+s.charAt(largo-1-i);
			hashing[i] = hashing[i+1]*b+s.charAt(i);
		}
		long[] acumulado = new long[largo];
		for(int i=0; i<largo; i++){
			long anterior = 0;
			if(i>0) anterior = acumulado[i-1];
			long actual = 0;
		    for(int j = 0; j<=i; j++){
		    	if(palindrome(j,i)){
		    		actual++;
		        }
		    }
		    acumulado[i]=actual+anterior;
		}
		long[] dp= new long[largo];
		if(largo==1) System.out.println("0");
		else{
			for(int i=1;i<largo;i++){
				long aux = 0;
				for(int j=1;j<=i;j++){
					if (palindrome(j,i)){
						aux+=acumulado[j-1];
					}
				}
				dp[i]=dp[i-1]+aux;
			}
			System.out.println(dp[largo-1]);
		}
	}
	public static boolean palindrome(int i, int j){
		long hash1,hash2;
		if(j!=largo-1) hash1 = hashing[i]-hashing[j+1]*potencias[j-i+1];
		else hash1=hashing[i];
		if(i!=0) hash2= ihashing[j]-ihashing[i-1]*potencias[j-i+1];
		else hash2=ihashing[j];
		return hash1==hash2;
	}
}