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

public class CO_159D
{
	static int imax=Integer.MAX_VALUE,imin=Integer.MIN_VALUE;
	static long lmax=Long.MAX_VALUE,lmin=Long.MIN_VALUE;
	public static void main (String[] args) throws java.lang.Exception
	{
	
	//	Scanner scan=new Scanner(System.in);
		InputReader in =new InputReader(System.in);
		PrintWriter out=new PrintWriter(System.out);
//		int t=in.nextInt();
 		int t=1;
		while(t-->0){
			int i=0,j=0;	
			String str=in.next();
			int n=str.length();
			boolean val[][]=new boolean[n][n];
			for(i=0;i<n;i++){
				val[i][i]=true;
			}
			int left[]=new int[n];
			int right[]=new int[n];
			Arrays.fill(left,1);
			Arrays.fill(right,1);
			for(int l=2;l<=n;l++){
				i=0;
				for(j=l-1;j<n;j++,i++){
					if(l==2){
						if(str.charAt(i)==str.charAt(j)){
							left[i]++;right[j]++;
							val[i][j]=true;
						}
					}else{
//						System.out.println(i+" jj "+j);
						if((str.charAt(i)==str.charAt(j)) && (val[i+1][j-1]==true)){
							val[i][j]=true;
							left[i]++;right[j]++;
//							System.out.println(i+" "+j);
						}
					}
				}
//				System.out.println(l);
			}
//			System.out.println(Arrays.toString(right));
			for(i=n-2;i>=0;i--){
				left[i]+=left[i+1];
			}
//			System.out.println(Arrays.toString(left));
			long ans=0;
			for(i=0;i<n-1;i++){
				ans+=(right[i]*left[i+1]);
			}
			out.println(ans);
		}
	out.close();
	}
	
	
	static class InputReader
	{
	 
	    private InputStream stream;
	    private byte[] buf = new byte[1024];
	    private int curChar;
	    private int numChars;
	 
	    public InputReader(InputStream stream) {
	        this.stream = stream;
	    }
	 
	    public int read() {
	        if (numChars == -1)
	            throw new InputMismatchException();
	        if (curChar >= numChars) {
	            curChar = 0;
	            try {
	                numChars = stream.read(buf);
	            } catch (IOException e) {
	                throw new InputMismatchException();
	            }
	            if (numChars <= 0)
	                return -1;
	        }
	        return buf[curChar++];
	    }
	 
	    public int nextInt() {
	        int c = read();
	        while (isSpaceChar(c))
	            c = read();
	        int sgn = 1;
	        if (c == '-') {
	            sgn = -1;
	            c = read();
	        }
	        int res = 0;
	        do {
	            if (c < '0' || c > '9')
	                throw new InputMismatchException();
	            res *= 10;
	            res += c & 15;
	            c = read();
	        } while (!isSpaceChar(c));
	        return res * sgn;
	    }
	 
	    public long nextLong() {
	        int c = read();
	        while (isSpaceChar(c))
	            c = read();
	        int sgn = 1;
	        if (c == '-') {
	            sgn = -1;
	            c = read();
	        }
	        long res = 0;
	        do {
	            if (c < '0' || c > '9')
	                throw new InputMismatchException();
	            res *= 10;
	            res += c & 15;
	            c = read();
	        } while (!isSpaceChar(c));
	        return res * sgn;
	    }
	 
	    public String next() {
	        int c = read();
	        while (isSpaceChar(c))
	            c = read();
	        StringBuilder res = new StringBuilder();
	        do {
	            res.appendCodePoint(c);
	            c = read();
	        } while (!isSpaceChar(c));
	        return res.toString();
	    }
	 
	    public String nextLine() {
	        int c = read();
	        //while (c != '\n' && c != '\r' && c != '\t' && c != -1)
	        //c = read();
	        StringBuilder res = new StringBuilder();
	        do {
	            res.appendCodePoint(c);
	            c = read();
	        } while (c != '\n' && c != '\r' && c != '\t' && c != -1);
	        return res.toString();
	    }
	 
	    public static boolean isSpaceChar(int c) {
	        return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
	    }
	 
	}   

}