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.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
//import sun.security.krb5.internal.KDCOptions;
public class Main
{
  public static void main(String[] args) throws IOException
  {
     new Main().run();
  }


  StreamTokenizer in;
  PrintWriter out;
  int d1[];
  int d2[];
  String s;
  String nextString() throws IOException
  {
     in.nextToken();
     return (String)in.sval;
  }

  int nextInt() throws IOException
  {
     in.nextToken();

     return (int)in.nval;
  }

  long nextLong() throws IOException
  {
     in.nextToken();

     return (long)in.nval;
  }
  void run() throws IOException
  {
     in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
     out = new PrintWriter(new OutputStreamWriter(System.out));
     solve();
     out.flush();
  }
  void solve() throws IOException
  {
      s = nextString();
      int n = s.length();
      long otv = 0;
      d1 = new int[n];
      d2 = new int[n];
      chet(n);
      nech(n);
      for(int i=0; i<n; i++){
       for(int j=i+1; j<n; j++){
        int x = d1[i] + 1;
        int y = d1[j] + 1;
        x = Math.min(x, j - i + 1);
        y = Math.min(y, j - i + 1);
        if (j - i + 1 >= x + y){
         otv += (long)(x * y);
        } else {
         otv += (long)((j - i + 1 - y) * y);
         long t = x - j + i - 1 + y;
         t = (t * (2 *y - t - 1)) / 2;
         otv += t;
        }
        x = d1[i] + 1;
        y = d2[j];
        x = Math.min(x, j - i);
        y = Math.min(y, j - i);
        if (j - i>= x + y){
         otv += (long)(x * y);
        } else {
         otv += (long)((j - i- y) * y);
         long t = x - j + i + y;
         t = (t * (2 *y - t - 1)) / 2;
         otv += t;
        }
        x = d2[i];
        y = d1[j] + 1;
        x = Math.min(x, j - i + 1);
        y = Math.min(y, j - i + 1);
        if (j - i + 1>= x + y){
         otv += (long)(x * y);
        } else {
         otv += (long)((j - i - y + 1) * y);
         long t = x - j + i - 1 + y;
         t = (t * (2 *y - t - 1)) / 2;
         otv += t;
        }
        x = d2[i];
        y = d2[j];
        x = Math.min(x, j - i);
        y = Math.min(y, j - i);
        if (j - i>= x + y){
         otv += (long)(x * y);
        } else {
         otv += (long)((j - i- y) * y);
         long t = x - j + i + y;
         t = (t * (2 *y - t - 1)) / 2;
         otv += t;
        }
       }
      }
      out.print(otv);
  }

  void nech(int n){
    int l = 0; 
    int r =-1;
    for (int i=0; i<n; i++){
     int k;
     if (i>r){
      k=1;
     }else {
      k = (Math.min(d1[l+r-i], (r-i))) + 1;
     }
     while(i+k < n && i-k >= 0 && s.charAt(k+i) == s.charAt(i-k)){
      k++;
     }
     k--;
     d1[i]= k;
     if (i+k>r){
      l=i-k;
      r=i+k;
     }
    }
  }
  void chet(int n){
   int l = 0;
   int r = -1;
   for (int i=0; i<n; i++){
    int k;
    if (i>r){
     k=1;
    }else {
     k = (Math.min(d2[l+r-i+1], (r-i+1)))+1;
    }
    while(i+k-1 < n && i-k >= 0 && s.charAt(i+k-1) == s.charAt(i-k)){
     k++;
    }
    k--;
    d2[i]=k;
    if(i+k-1 > r){
     l = i-k;  
     r = i+k-1;
    }
   }
  }
}