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.util.*;

/**
 *
 * @author Alejandro E. Garces
 */
public class Main{
    
    static class Pair{
        
        int i, j;
        Pair(int ii, int jj)
        {
            i = ii;
            j = jj;
        }
        
    }
    static boolean isPalindrome(String x)
    {
        //
        int n = x.length();
        for(int i = 0; i < n/2; i++)
            if(x.charAt(i) != x.charAt(n - i - 1))
                return false;
        //System.out.println(x);
        return true;
    }
    
    static Boolean[][] isPalin;
    static int n;
    static String line;
    static void fill(int i, int j)
    {
        if(i > j)return;
        palin(i, j);
        palin(i + 1, j);
        palin(i, j - 1);
        palin(i + 1, j - 1);
    }
    
    static boolean palin(int i, int j)
    {
        if(i > j)return true;
        if(isPalin[i][j] != null) return isPalin[i][j];
        return isPalin[i][j] = (line.charAt(i) == line.charAt(j)) & palin( i + 1 ,  j -1);
    }
   public static void main(String[] args) throws IOException{
         //String file = "test";  
        //System.setIn(new FileInputStream(file+".txt"));
        //System.setOut(new PrintStream(new FileOutputStream(file+"O.txt")));
         BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
         line = in.readLine();
         n = line.length();
         //System.out.println(n);
         ArrayList<Pair> pairs = new ArrayList<Pair>();
         long answer = 0;
         if(n == 1)answer = 1;
         else{
         isPalin = new Boolean[n + 1][n + 1];
         //Arrays
         int[] freq = new int[n + 1];
         int[] acum = new int[n + 1];
         fill(0, n - 1);
         for(int i = 0; i < n; i++)
             for(int j = i ; j < n ; j++)
                 if(palin(i, j))
                  //palinif(isPalin[i][j] != null && isPalin[i][j] == true)
                 {
                     freq[i]++;
                     //isPalin[i][j] = true;
                     pairs.add(new Pair(i, j));
                 }
         
          
         for(int i = 1; i <= n; i++)
             acum[i] = acum[i-1] + freq[i-1];
         
         //System.out.println(Arrays.toString(freq));
         //System.out.println(Arrays.toString(acum));
         
         for(Pair x:pairs)
         {
             int aux = (acum[n] - acum[x.j+1]);
                     //System.out.println(x.i + " - "+ x.j + " - "+aux);
                     answer+= aux;
         }
         /*for(int i = 0; i < n; i++)
             for(int j = i + 1; j <= n ; j++)
                 if(isPalin[i][j])
                 {
                     int aux = (acum[n] - acum[j]);
                     //System.out.println(i + " - "+ j + " - "+aux);
                     answer+= aux;
                 }
         */
        
         }
         System.out.println(answer);
         in.close();
         System.exit(0);
     }
}