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

import javax.xml.parsers.DocumentBuilder;
import javax.xml.parsers.DocumentBuilderFactory;
import javax.xml.parsers.ParserConfigurationException;
import javax.xml.xpath.XPath;
import javax.xml.xpath.XPathConstants;
import javax.xml.xpath.XPathExpression;
import javax.xml.xpath.XPathExpressionException;
import javax.xml.xpath.XPathFactory;

import org.w3c.dom.Document;
import org.w3c.dom.NodeList;
import org.xml.sax.InputSource;
import org.xml.sax.SAXException;

import com.sun.org.apache.xerces.internal.xni.XMLString;

public class E
{
	String line;
	StringTokenizer inputParser;
	BufferedReader is;
	FileInputStream fstream;
	DataInputStream in;
	
	void openInput(String file)
	{

		if(file==null)is = new BufferedReader(new InputStreamReader(System.in));//stdin
		else
		{
			try{
		
				
			fstream = new FileInputStream(file);
			in = new DataInputStream(fstream);
			is = new BufferedReader(new InputStreamReader(in));
			}catch(Exception e)
			{
				System.err.println(e);
			}
		}

	}
	
	void readNextLine()
	{
		try {
			line = is.readLine();
			inputParser = new StringTokenizer(line, " ");
			//System.err.println("Input: " + line);
		} catch (IOException e) {
			System.err.println("Unexpected IO ERROR: " + e);
		}	
		
	}
	
	int NextInt()
	{
		String n = inputParser.nextToken();
		int val = Integer.parseInt(n);
		
		//System.out.println("I read this number: " + val);
		return val;
	}
	
	String NextString()
	{
		String n = inputParser.nextToken();
		return n;
	}
	
	void closeInput()
	{
		try {
			is.close();
		} catch (IOException e) {
			System.err.println("Unexpected IO ERROR: " + e);
		}
			
	}
	
	public static void main(String [] argv)
	{
		String filePath=null;
		if(argv.length>0)filePath=argv[0];
		new E(filePath);
	}

	
	int N;
	int [] start,end;
	String s;
	boolean [][]p;
	public E(String inputFile) 
	{
		openInput(inputFile);
		
		readNextLine();
		s=line;

		N=s.length();
		start = new int[N];
		end=new int[N];
		p=new boolean[N][N];
		fill();

		for(int i=0; i<N; i++)
		{
			for(int j=i; j<N; j++)
			{
				if(p[i][j])
				{
					start[i]++;
					end[j]++;
				}
				
			}
		}
		long ret=0;
		for(int i=0; i<N-1; i++)
		{
			for(int j=i+1; j<N; j++)
				ret+=(long)end[i]*(long)start[j];
		}
		System.out.println(ret);
        closeInput();		

        

		
	}
	
	private void fill() {
		for(int d=1; d<=N; d++)
		{
			for(int a=0; a<N; a++)
			{
				if(a+d>N)break;
				if(d==1)
				{
					p[a][a]=true;
					continue;
				}
				else if (d==2)
				{
					p[a][a+d-1]=(s.charAt(a)==s.charAt(a+d-1));
				}
				else
				{
					if((s.charAt(a)==s.charAt(a+d-1)))p[a][a+d-1]=p[a+1][a+d-2];
					else p[a][a+d-1]=false;
				}
			}
		}
	}
	
	

	
}