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.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.BitSet;
import java.util.StringTokenizer;


public class sol {
	//...................... Global Variables .......................//
	static BitSet prime;             // used in seive generation
	// true = not prime     and false = prime
	//...................... Global Variables .......................//
	
	
	
	
	
	//===================  PROBLEM SOLVING COMES HERE ===== START  ====================//
	
    void solve() throws IOException, Exception {
    	
    	char s[] = in.next().toCharArray();
    	Manacher man = new Manacher(s);
		    	
		  /*  	for(int i =2; i< man.t.length-2;i++){
		    		System.out.print(man.t[i] + " ");
		    	}System.out.println();
		    	for(int i =0; i< man.p.length;i++){
		    		System.out.print(man.p[i] + " ");
		    	}System.out.println();
		    */	
		    	
		    	
		    	int n = s.length;
				int start[] = new int[n + 1];
				int end[] = new int[n + 1];

				for (int i = 0,j = 0; i < man.p.length; i += 2, j++) {
						start[j + 1]--;
						start[j - man.p[i]/2]++;
						end[j]++;
						end[j + man.p[i]/2 + 1]--;
				}
				
				for(int i = 1,j = 0; i < man.p.length; i += 2, j++){
					start[j + 1]--;
					start[j - man.p[i]/2 + 1]++;
					end[j + 1]++;
					end[j + 1 + man.p[i]/2]--;
				}

							/*	for(int i = 0;i<n+1;i++){
									System.out.print(start[i] + " ");
								}System.out.println();
								for(int i = 0;i<n+1;i++){
									System.out.print(end[i] + " ");
								}
								System.out.println("\n\n");
							*/
				for (int i = 1; i < n; i++) {
					start[i] += start[i - 1];
					end[i] += end[i - 1];
				}
				
				
							/*	for(int i = 0;i<n+1;i++){
									System.out.print(start[i] + " ");
								}System.out.println();
								for(int i = 0;i<n+1;i++){
									System.out.print(end[i] + " ");
								}
								System.out.println("\n\n");
							*/
				
				for (int i = n - 2; i >= 0; i--)
					start[i] += start[i + 1];
								
							/*	for(int i = 0;i<n+1;i++){
									System.out.print(start[i] + " ");
								}System.out.println();
								for(int i = 0;i<n+1;i++){
									System.out.print(end[i] + " ");
								}
								System.out.println("\n\n");
							*/	
				long ans = 0;
				for (int i = 0; i < n - 1; i++)
					{ //  System.out.println(end[i] + "  " +  start[i + 1] + " *  = " + end[i] * start[i + 1] );
						ans += end[i] * start[i + 1];
					}
				out.println(ans);
    	
    	
    }
    
    //===================  PROBLEM SOLVING COMES HERE ===== END ======================//
    
    
    
    
    
    
    public static void main(String[] args) throws FileNotFoundException, IOException, Exception {
    	
    	//--------------------------------- Console I/O ------------------------------//
    	   in = new FastScanner(new BufferedReader(new InputStreamReader(System.in)));
           out = new PrintWriter(System.out);
    	//--------------------------------- Console I/O ------------------------------//
    	
    	
    	//--------------------------------- File I/O ---------------------------------//
        //   in = new FastScanner(new BufferedReader(new FileReader("input.txt")));
        //   out = new PrintWriter(new FileWriter("output.txt"));
        //--------------------------------- File I/O ---------------------------------//
        new sol().solve();
        out.close();
    }
    
    //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Useful Methods START ~~~~~~~~~~~~~~~~~~~~~~~~~~~~//
    //Manacher code
    static public class Manacher {
    	private int[] p;   // p[i] = longest palndromic substring whose centre is i
    	private char s[];  // original string
    	private char t[];  // transformed string
    	
    	public Manacher(char[] s){
    		this.s = s;
    		preprocess();
    		p =new int[t.length];
  
    		int center=0, right=0;
    		for(int i=1; i<t.length-1; i++){
    			int mirror = 2 * center - i;
    			
    			if(i < right)
    				p[i] = Math.min(right - i, p[mirror]);
    			
    			while(t[i - (1 + p[i])] == t[i + (1 + p[i])])
    				p[i]++;
    			
    			if(i + p[i] > right){
    				center = i;
    				right = i + p[i];
    			}
    		}

    		int ans[] = new int[p.length - 4];
			for (int i = 2; i < p.length - 2; i++)
				ans[i - 2] = p[i];

			p = ans;
			
    	}
    	
    	// convert abababa    to   $#a#b#a#b#a#b#a#@ <= transformed string
    	private void preprocess(){
    		t = new char[s.length*2 + 3];    // 2n +1 +2 for ("$","@")
    		t[0] = '$';
    		for(int i = 0;i<s.length;i++){
    			t[2 * i + 1] = '#';
    			t[2 * i + 2] = s[i];
    		}
    		t[s.length*2 + 1] = '#';
    		t[s.length*2 + 2] = '@';
    		
    	}
    }
// End of Manacher code
    
    //Modular Exponentiation
	    public static long modPow(long base,long power, long m)   // with mod
	    {  // long m = (long) 1e9+7;
	    	long  result = 1;
	    	if(power==0)  return 1;
	    	if(power==1)  return base;
	    	while(power>0)
	    	{
	    	    if(power%2==1)
	    	        result = (result * base) % m;
	    	    power = power >> 1;     // divide by 2
	    	    base = (base * base) % m;
	    	}
	    	return result;
	    } 
	    
	    public static long pow(long base,long power)              // without mod
	    { 
	    	long  result = 1;
	    	if(power==0)  return 1;
	    	if(power==1)  return base;
	    	while(power>0)
	    	{
	    	    if(power%2==1)
	    	        result = result * base;
	    	    power = power >> 1;     // divide by 2
	    	    base = base * base;
	    	}
	    	return result;
	    } 
	 // END Modular Exponentiation 
	    
	    
	 // GCD && LCM 
		public static long gcd(long a ,long b){ return b == 0 ? a : gcd(b , a % b); }
		public static long lcm(long a , long b){ return a*(b/gcd(a, b)); }   
		
	 // Count Number of One's in any number
		public static int countOnes(long n){ int count = 0;
			while(n>0){
				n = n & (n-1);
				count++;
			} return count; }
	
	//Pair Compare
		static class Pair implements Comparable<Pair>
		{
			int a,b;
			Pair (int a,int b)
			{
				this.a=a;
				this.b=b;
			}
		 
			public int compareTo(Pair o) {
				// TODO Auto-generated method stub
				if(this.a!=o.a)
				    return Integer.compare(this.a,o.a);
				else
					return Integer.compare(this.b, o.b);
				//return 0;
			}
			public boolean equals(Object o) {
		        if (o instanceof Pair) {
		            Pair p = (Pair)o;
		            return p.a == a && p.b == b;
		        }
		        return false;
		    }
		    public int hashCode() {
		        return new Integer(a).hashCode() * 31 + new Integer(b).hashCode();
		    }
		    
		} 
		
		
		
	 // Sieve of erothenese
		 public static void sieve(int UB){
			//ar = new ArrayList();
			  prime = new BitSet(UB+1);
			  prime.set(0);
			  prime.set(1);
			  for(int i = 2; i*i <= UB; i++){
				if(prime.get(i) == false){
					for(int j = i*i ; j <= UB ; j += i)
						prime.set(j);
				}
			  }
				/* for(int i = 2; i <= UB; i++){
				      if(!bs[i])ar.add(i);
				}*/
		 }
		 // usage hint : if prime.get(i)  == false    then  i is prime
    
    //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Useful Methods END ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~//

    static FastScanner in;
    static PrintWriter out;

    static class FastScanner {
        BufferedReader in;
        StringTokenizer st;

        public FastScanner(BufferedReader in) {
            this.in = in;
        }

        public String nextToken() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(in.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        public int nextInt() { return Integer.parseInt(nextToken()); }
        public long nextLong() { return Long.parseLong(nextToken()); }
        public double nextDouble() { return Double.parseDouble(nextToken()); }
        public BigInteger BigInteger()throws Exception { return new BigInteger(nextToken()); }
        public String next() throws IOException { return nextToken(); }
        public String nextLine() throws IOException { return in.readLine(); }
        
    }
}