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 H245 {
 
	public static void main(String[] args) throws Exception{
 
		// TODO Auto-generated method stub
 		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
 		PrintWriter out = new PrintWriter(System.out);
 		String input = bf.readLine().trim();
 		boolean [][] isPal = new boolean[input.length()][input.length()];
 		for(int i = 0;i<input.length();i++){
 			isPal[i][i] = true;
 			if (i >=1)
 				isPal[i][i-1] = true;
 		}
 		for(int len = 2;len<=input.length();len++){
 			for(int start = 0;start<input.length()-len+1;start++){
 				isPal[start][start+len-1] = isPal[start+1][start+len-2] && (input.charAt(start) == input.charAt(start+len-1));
 			}
 		}
 		
 		int[] startingindex = new int[input.length()];
 		for(int i = 0;i<input.length();i++){
 			int count = 0;
 			for(int j = i;j<input.length();j++){
 				if (isPal[i][j] == true)
 					count+=1;
 			}
 			startingindex[i] = count;
 		}
 		
 		int[] endingindex = new int[input.length()];
 		for(int i = 0;i<input.length();i++){
 			int count = 0;
 			for(int j = 0;j<=i;j++){
 				if (isPal[j][i] == true)
 					count+=1;
 			}
 			endingindex[i] = count;
 		}
 		long total = 0;
 		for(int diff = 1;diff < input.length();diff++){
 			for(int start = 0;start < input.length()-diff;start++){
 				total+= endingindex[start] * startingindex[start+diff];
 			}
 		}
 		
 		
 		out.println(total);
 		
 		
 		out.close();
 		
 		
 		
 		
	}
 
 }
	
 	
// 
////StringJoiner sj = new StringJoiner(" "); 
////sj.add(strings)
////sj.toString() gives string of those stuff w spaces or whatever that sequence is
//class BinaryIndexedTree 
//{  
//    // Max tree size 
//    final static int MAX = 1000005;      
//  
//    static int BITree[] = new int[MAX];     
//    /* n --> No. of elements present in input array.  
//    BITree[0..n] --> Array that represents Binary  
//                    Indexed Tree. 
//    arr[0..n-1] --> Input array for which prefix sum  
//                    is evaluated. */
//  
//    // Returns sum of arr[0..index]. This function  
//    // assumes that the array is preprocessed and  
//    // partial sums of array elements are stored  
//    // in BITree[]. 
//    int getSum(int index){ 
//        int sum = 0;
//        index = index + 1; 
//        while(index>0){ 
//            sum += BITree[index]; 
//            index -= index & (-index); 
//        } 
//        return sum; 
//    } 
//    public static void updateBIT(int n, int index, int val){ 
//        index = index + 1; 
//        while(index <= n){ 
//	        BITree[index] += val; 
//	        index += index & (-index); 
//        } 
//    } 
//    void constructBITree(int arr[], int n){ 
//        for(int i=1; i<=n; i++) 
//            BITree[i] = 0; 
//        for(int i = 0; i < n; i++) 
//            updateBIT(n, i, arr[i]); 
//    } 
//}