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

public class P159D {

  long [][] prepareHashTable(String s) { // O(n^2)
    final long HASH_PARAM = 31; // java's hash code param

    int n = s.length();
    long [][] hashTable = new long [n][n];

    for (int i = 0; i < n; i++) {
      hashTable[i][i] = s.charAt(i);
    }

    for (int i = 1; i < n; i++) {
      for (int j = i - 1; j >= 0; j--) {
        hashTable[j][i] = hashTable[j][i - 1] * HASH_PARAM + hashTable[i][i];
      }
    }

    for (int i = n - 2; i >= 0; i--) {
      for (int j = i + 1; j < n; j++) {
        hashTable[j][i] = hashTable[j][i + 1] * HASH_PARAM + hashTable[i][i];
      }
    }

    return hashTable;
  }

  @SuppressWarnings("unchecked")
  public void run() throws Exception {
    String s = next();
    int n = s.length();
    long [][] ht = prepareHashTable(s);

    long [] pc = new long [n + 1];
    for (int l = n - 1; l > 0; l--) {
      for (int r = l; r < n; r++) {
        if (ht[l][r] == ht[r][l]) {
          pc[l]++;
        }
      }
      pc[l] += pc[l + 1];
    }

    long count = 0;
    for (int l = 0; l < n - 1; l++) {
      for (int r = l; r < n - 1; r++) {
        if (ht[l][r] == ht[r][l]) {
          count += pc[r + 1];
        }
      }
    }

    println(count);
  }

  public static void main(String... args) throws Exception {
    br = new BufferedReader(new InputStreamReader(System.in));
    pw = new PrintWriter(new BufferedOutputStream(System.out));
    new P159D().run();
    br.close();
    pw.close();
  }

  static BufferedReader br;
  static PrintWriter pw;
  StringTokenizer stok;

  String nextToken() throws IOException {
    while (stok == null || !stok.hasMoreTokens()) {
      String s = br.readLine();
      if (s == null) {
        return null;
      }
      stok = new StringTokenizer(s);
    }
    return stok.nextToken();
  }

  void print(byte b) {
    print("" + b);
  }

  void print(int i) {
    print("" + i);
  }

  void print(long l) {
    print("" + l);
  }

  void print(double d) {
    print("" + d);
  }

  void print(char c) {
    print("" + c);
  }

  void print(Object o) {
    if (o instanceof int[]) {
      print(Arrays.toString((int [])o));
    } else if (o instanceof long[]) {
      print(Arrays.toString((long [])o));
    } else if (o instanceof char[]) {
      print(Arrays.toString((char [])o));
    } else if (o instanceof byte[]) {
      print(Arrays.toString((byte [])o));
    } else if (o instanceof short[]) {
      print(Arrays.toString((short [])o));
    } else if (o instanceof boolean[]) {
      print(Arrays.toString((boolean [])o));
    } else if (o instanceof float[]) {
      print(Arrays.toString((float [])o));
    } else if (o instanceof double[]) {
      print(Arrays.toString((double [])o));
    } else if (o instanceof Object[]) {
      print(Arrays.toString((Object [])o));
    } else {
      println("" + o);
    }
  }

  void print(String s) {
    pw.print(s);
  }

  void println(byte b) {
    println("" + b);
  }

  void println(int i) {
    println("" + i);
  }

  void println(long l) {
    println("" + l);
  }

  void println(double d) {
    println("" + d);
  }

  void println(char c) {
    println("" + c);
  }

  void println(Object o) {
    print(o);
    println("");
  }

  void println(String s) {
    pw.println(s);
  }

  int nextInt() throws IOException {
    return Integer.parseInt(nextToken());
  }

  long nextLong() throws IOException {
    return Long.parseLong(nextToken());
  }

  double nextDouble() throws IOException {
    return Double.parseDouble(nextToken());
  }

  char nextChar() throws IOException {
    return (char) (br.read());
  }

  String next() throws IOException {
    return nextToken();
  }

  String nextLine() throws IOException {
    return br.readLine();
  }

  int [] readInt(int size) throws IOException {
    int [] array = new int [size];
    for (int i = 0; i < size; i++) {
      array[i] = nextInt();
    }
    return array;
  }

  long [] readLong(int size) throws IOException {
    long [] array = new long [size];
    for (int i = 0; i < size; i++) {
      array[i] = nextLong();
    }
    return array;
  }

  double [] readDouble(int size) throws IOException {
    double [] array = new double [size];
    for (int i = 0; i < size; i++) {
      array[i] = nextDouble();
    }
    return array;
  }

}