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.lang.Math;
import java.util.*;

public class Main
{	
	public BufferedReader in;
	public PrintStream out;
	
	public boolean log_enabled = true;
	
	public void test()
	{
		String s = readLn();
		int n = s.length();
		
		long[] begin = new long[n];
		long[] end = new long[n];
		
		Arrays.fill(begin, 1);
		Arrays.fill(end, 1);
		
		long mod = Long.parseLong("10822631340427");
		
		long[] hash1 = new long[n+1];
		long[] hash2 = new long[n+1];
		
		long[] new_hash1 = new long[n+1];
		long[] new_hash2 = new long[n+1];
		
		long[] buf;
		
		int i,k;
		
		for (i=0; i<n; i++)
		{
			new_hash1[i] = s.charAt(i)-'a';
			new_hash2[i] = s.charAt(i)-'a';
		}
		
		for (k=0; k<n; k++)
		{
			if (k>0)
			{
				for (i=k; i<n; i++)
				{
					new_hash1[i] = (hash1[i-1]*26 + s.charAt(i) - 'a') % mod;
				}
				
				for (i=0; i<n-k; i++)
				{
					new_hash2[i] = (hash2[i+1]*26 + s.charAt(i) - 'a') % mod;
				}
			}
			
			buf = new_hash1;
			new_hash1 = hash1;
			hash1 = buf;
			buf = new_hash2;
			new_hash2 = hash2;
			hash2 = buf;
			
			for (i=k; i+1<n-k; i++)
			{
				if (hash1[i] == hash2[i+1])				
				{
					end[i+k+1]++;
					begin[i-k]++;
				}
			}
			
			for (i=k; i+2<n-k; i++)
			{
				if (hash1[i] == hash2[i+2])
				{
					end[i+k+2]++;
					begin[i-k]++;
				}
			}
		}
		
		for (i=n-1; i>0; i--)		
		{
			begin[i-1] += begin[i];
		}
		
		long r = 0;
		
		for (i=1; i<n; i++)
		{
			r += end[i-1]*begin[i];
		}
		
		out.println(r);
		
		/*
		for (i=0; i<n; i++)
		{
			out.print(begin[i]);out.print(" ");
		}
		
		out.println();
		
		for (i=0; i<n; i++)
		{
			out.print(end[i]);out.print(" ");
		}*/
		
	}
	
    
	public void run()
	{
		try
		{
			in = new BufferedReader(new InputStreamReader(System.in));
			out = System.out;
			
			//in = new BufferedReader(new FileReader("in.txt"));
			//out = new PrintStream(new File("out.txt"));
			
			
		}
		catch (Exception e)
		{
			return;
		}
		
		//while (true)
		{
			//int t = readInt(); for (int i=0; i<t; i++)					
			{
				test();
			}
		}
	}
	
	public static void main(String args[])
	{
		new Main().run();
	}
	
	private StringTokenizer tokenizer = null;
	
	public int readInt() 
	{
        return Integer.parseInt(readToken());
    }
   
    public long readLong() 
	{
        return Long.parseLong(readToken());
    }
   
    public double readDouble() 
	{
        return Double.parseDouble(readToken());
    }
   
	public String readLn()
	{	
		try
		{
			String s;
			while ((s = in.readLine()).length()==0);
			return s;
		}
		catch (Exception e)
		{
			return "";
		}
	}
	
    public String readToken() 
	{
		try
		{
			while (tokenizer == null || !tokenizer.hasMoreTokens()) 
			{
				tokenizer = new StringTokenizer(in.readLine());
			}
			return tokenizer.nextToken();
		}
		catch (Exception e)
		{
			return "";
		}
    }
	
	public int[] readIntArray(int n)
	{
		int[] x = new int[n];
		readIntArray(x, n);
		return x;
	}
	
	public void readIntArray(int[] x, int n)
	{
		for (int i=0; i<n; i++)
		{
			x[i] = readInt();
		}
	}
	
	public void logWrite(String format, Object... args)
	{
		if (!log_enabled)
		{
			return;
		}
		
		out.printf(format, args);
	}
}