#include <bits/stdc++.h>
using namespace std;
long long convertToNum(string s) {
  long long val = 0;
  for (int i = 0; i < (s.size()); i++) val = val * 10 + s[i] - '0';
  return val;
}
char bu[50];
string convertToString(int a) {
  sprintf(bu, "%d", a);
  return string(bu);
}
long long GCD(long long x, long long y) {
  if (!x) return y;
  if (!y) return x;
  if (x == y) return x;
  if (x < y)
    return GCD(x, y % x);
  else
    return GCD(x % y, y);
}
long long POW(long long x, long long y, long long Base) {
  if (!y) return 1;
  long long u = POW(x, y / 2, Base);
  u = (u * u) % Base;
  if (y & 1)
    return (u * x) % Base;
  else
    return u;
}
void extended_euclid(long long A, long long B, long long &x, long long &y) {
  if (A == 1 && B == 0) {
    x = 1;
    y = 0;
    return;
  }
  if (A < B)
    extended_euclid(B, A, y, x);
  else {
    long long xx, yy;
    extended_euclid(A % B, B, xx, yy);
    x = xx;
    y = yy - (A / B) * xx;
  }
}
int N, M, tmp, minR = 996;
double C, first, X;
vector<int> v;
std::map<int, int> myMap;
string st;
vector<vector<unsigned long long> > f;
vector<unsigned long long> endAt, startAt;
int main() {
  cin >> st;
  for (int i = 0; i < st.size(); i++) v.push_back(0);
  vector<unsigned long long> f0;
  int n = st.size();
  for (int i = 0; i < n; i++) endAt.push_back(0);
  for (int i = 0; i < n; i++) startAt.push_back(0);
  for (int i = 0; i < (n); i++) {
    f0.clear();
    for (int i = 0; i < n; i++) f0.push_back(0);
    f.push_back(f0);
  }
  for (int i = 0; i < (n); i++) {
    f[i][i] = 1;
  }
  int startI, startJ;
  if (n % 2 == 0) {
    startI = n / 2 - 1;
    startJ = n / 2;
  } else {
    startI = n / 2;
    startJ = n / 2;
  }
  for (int i = (n - 1); i >= (0); i--) {
    for (int j = (0); j <= (n - 1); j++) {
      bool x;
      if (f[i][j]) continue;
      if (i == n - 1)
        x = true;
      else if (j == 0)
        x = true;
      else if (j - i == 1)
        x = true;
      else
        x = f[i + 1][j - 1] ? true : false;
      f[i][j] = (st[i] == st[j] && x) ? 1 : 0;
    }
  }
  startAt[n - 1]++;
  for (int i = 0; i < (n - 1); i++) {
    for (int j = (i); j <= (n - 1); j++) {
      if (f[i][j] == 1) {
        endAt[j]++;
        startAt[i]++;
      }
    }
  }
  unsigned long long count = 0;
  for (int i = 0; i < (n - 1); i++) {
    unsigned long long l = endAt[i];
    unsigned long long r = 0;
    for (int j = (i + 1); j <= (n - 1); j++) {
      r += startAt[j];
    }
    count += r * l;
  }
  cout << count;
  return 0;
}

### Prompt

Develop a solution in Cpp to the problem described below:

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

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
long long convertToNum(string s) {
  long long val = 0;
  for (int i = 0; i < (s.size()); i++) val = val * 10 + s[i] - '0';
  return val;
}
char bu[50];
string convertToString(int a) {
  sprintf(bu, "%d", a);
  return string(bu);
}
long long GCD(long long x, long long y) {
  if (!x) return y;
  if (!y) return x;
  if (x == y) return x;
  if (x < y)
    return GCD(x, y % x);
  else
    return GCD(x % y, y);
}
long long POW(long long x, long long y, long long Base) {
  if (!y) return 1;
  long long u = POW(x, y / 2, Base);
  u = (u * u) % Base;
  if (y & 1)
    return (u * x) % Base;
  else
    return u;
}
void extended_euclid(long long A, long long B, long long &x, long long &y) {
  if (A == 1 && B == 0) {
    x = 1;
    y = 0;
    return;
  }
  if (A < B)
    extended_euclid(B, A, y, x);
  else {
    long long xx, yy;
    extended_euclid(A % B, B, xx, yy);
    x = xx;
    y = yy - (A / B) * xx;
  }
}
int N, M, tmp, minR = 996;
double C, first, X;
vector<int> v;
std::map<int, int> myMap;
string st;
vector<vector<unsigned long long> > f;
vector<unsigned long long> endAt, startAt;
int main() {
  cin >> st;
  for (int i = 0; i < st.size(); i++) v.push_back(0);
  vector<unsigned long long> f0;
  int n = st.size();
  for (int i = 0; i < n; i++) endAt.push_back(0);
  for (int i = 0; i < n; i++) startAt.push_back(0);
  for (int i = 0; i < (n); i++) {
    f0.clear();
    for (int i = 0; i < n; i++) f0.push_back(0);
    f.push_back(f0);
  }
  for (int i = 0; i < (n); i++) {
    f[i][i] = 1;
  }
  int startI, startJ;
  if (n % 2 == 0) {
    startI = n / 2 - 1;
    startJ = n / 2;
  } else {
    startI = n / 2;
    startJ = n / 2;
  }
  for (int i = (n - 1); i >= (0); i--) {
    for (int j = (0); j <= (n - 1); j++) {
      bool x;
      if (f[i][j]) continue;
      if (i == n - 1)
        x = true;
      else if (j == 0)
        x = true;
      else if (j - i == 1)
        x = true;
      else
        x = f[i + 1][j - 1] ? true : false;
      f[i][j] = (st[i] == st[j] && x) ? 1 : 0;
    }
  }
  startAt[n - 1]++;
  for (int i = 0; i < (n - 1); i++) {
    for (int j = (i); j <= (n - 1); j++) {
      if (f[i][j] == 1) {
        endAt[j]++;
        startAt[i]++;
      }
    }
  }
  unsigned long long count = 0;
  for (int i = 0; i < (n - 1); i++) {
    unsigned long long l = endAt[i];
    unsigned long long r = 0;
    for (int j = (i + 1); j <= (n - 1); j++) {
      r += startAt[j];
    }
    count += r * l;
  }
  cout << count;
  return 0;
}

```