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;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.StringTokenizer;


public class E{
	
	static class FastReader 
    { 
        BufferedReader br; 
        StringTokenizer st; 
  
        public FastReader() 
        { 
            br = new BufferedReader(new
                     InputStreamReader(System.in)); 
        } 
  
        String next() 
        { 
            while (st == null || !st.hasMoreElements()) 
            { 
                try
                { 
                    st = new StringTokenizer(br.readLine()); 
                } 
                catch (IOException  e) 
                { 
                    e.printStackTrace(); 
                } 
            } 
            return st.nextToken(); 
        } 
  
        int nextInt() 
        { 
            return Integer.parseInt(next()); 
        } 
  
        long nextLong() 
        { 
            return Long.parseLong(next()); 
        } 
  
        double nextDouble() 
        { 
            return Double.parseDouble(next()); 
        } 
  
        String nextLine() 
        { 
            String str = ""; 
            try
            { 
                str = br.readLine(); 
            } 
            catch (IOException e) 
            { 
                e.printStackTrace(); 
            } 
            return str; 
        } 
    }
	
	static class Pair
	{
		int p;
		int q;
		Pair(int p,int q)
		{
			this.p = p;
			this.q = q;
		}
	}
	
	static int gcd(int a,int b)
	{
		if(a == 0) return b;
		if(b == 0) return a;
		
		return gcd(b,a%b);
	}
	
	
	public static void main(String[] args) 
	{
		OutputStream outputStream = System.out;
        FastReader sc = new FastReader();
        PrintWriter out = new PrintWriter(outputStream);
        
        String s = sc.nextLine();
        int n = s.length();
        boolean dp[][] = new boolean[n][n];
        
        for(int i = 0; i < n; i++)
        {
        	for(int j = 0; j < n; j++)
        	{
        		if(i == j) 
        		{
        			dp[i][j] = true;
        		}
        		else if(j == i+1 || j == i+2)
        		{
        			if(s.charAt(i) == s.charAt(j))
        			{
        				dp[i][j] = true;
        			}
        			else dp[i][j] = false;
        		}
        		else
        		{
        			dp[i][j] = false;
        		}
        	}
        }
        
       
        for(int ss = 3; ss < n; ss++)
        {
        	for(int i = 0; i < n; i++)
        	{	
        		int j = i+ss;
        		if(j >= n) break;
        		
        		if(dp[i+1][j-1] == true && (s.charAt(i) == s.charAt(j)))
        		{
        			dp[i][j] = true;
        		}
        		else dp[i][j] = false;
        	}
        }

        
        long cnt[] = new long[n];
        
        for(int i = n-1; i >= 0; i--)
        {	
        	if(i != n-1)
        	{
        		cnt[i] = cnt[i+1];
        	}
        	for(int j = i; j <= n-1; j++)
        	{
        		if(dp[i][j])
        		{
        			cnt[i]++;
        		}
        	}
        }
        
        long ans = 0L;
        for(int i = 0; i < n-1; i++)
        {
        	for(int j = i; j < n-1; j++)
        	{
        		if(dp[i][j])
        		{
        			ans += cnt[j+1];
        		}
        	}
        }
        
        out.println(ans);
        out.close();
	}

}