#include <bits/stdc++.h>
using namespace std;
long long bigmod(long long b, long long p) {
  if (p == 0) return 1;
  long long my = bigmod(b, p / 2);
  my *= my;
  my %= 1000000007;
  if (p & 1) my *= b, my %= 1000000007;
  return my;
}
int setb(int n, int pos) { return n = n | (1 << pos); }
int resb(int n, int pos) { return n = n & ~(1 << pos); }
bool checkb(int n, int pos) { return (bool)(n & (1 << pos)); }
int d1[5005], n;
char s[5005], str[5005];
void manodd() {
  int l = 0, r = -1;
  for (int i = 0; i < n; ++i) {
    int k = (i > r ? 1 : min(d1[l + r - i], r - i));
    while (i + k < n && i - k >= 0 && s[i + k] == s[i - k]) ++k;
    d1[i] = k--;
    if (i + k > r) l = i - k, r = i + k;
  }
}
void make() {
  int k = 0;
  s[k++] = '$';
  for (int i = 0; i < n; i++) {
    s[k++] = '#';
    s[k++] = str[i];
  }
  s[k++] = '#';
  s[k] = 0;
  n = k;
}
struct info {
  int l, r;
  info() {}
  info(int ll, int rr) {
    l = ll;
    r = rr;
  }
  bool operator<(const info &p) const {
    if (l == p.l)
      return r < p.r;
    else
      return l < p.l;
  }
};
vector<info> v;
int F(int x, int l) {
  int low = l, high = v.size() - 1, mid, ans = -1;
  while (low <= high) {
    mid = (low + high) / 2;
    int my = v[mid].l;
    if (my > x) {
      ans = mid;
      high = mid - 1;
    } else
      low = mid + 1;
  }
  if (ans == -1) return 0;
  return v.size() - ans;
}
int main() {
  scanf("%s", str);
  n = strlen(str);
  make();
  manodd();
  int len = strlen(str);
  for (int i = 0; i < len; i++) {
    int my = d1[(i + 1) * 2];
    my /= 2;
    int l = i, r = i;
    for (int j = 0; j < my; j++) {
      v.push_back(info(l, r));
      l--;
      r++;
    }
    if (i) {
      int my = d1[(i + 1) * 2 - 1];
      my = (my - 1) / 2;
      int l = i - 1;
      int r = i;
      for (int j = 0; j < my; j++) {
        v.push_back(info(l, r));
        l--;
        r++;
      }
    }
  }
  sort(v.begin(), v.end());
  long long ret = 0;
  for (int i = 0; i < v.size(); i++) {
    ret += F(v[i].r, i);
  }
  printf("%lld", ret);
  printf("\n");
  return 0;
}

### Prompt

In Cpp, your task is to solve the following 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

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
long long bigmod(long long b, long long p) {
  if (p == 0) return 1;
  long long my = bigmod(b, p / 2);
  my *= my;
  my %= 1000000007;
  if (p & 1) my *= b, my %= 1000000007;
  return my;
}
int setb(int n, int pos) { return n = n | (1 << pos); }
int resb(int n, int pos) { return n = n & ~(1 << pos); }
bool checkb(int n, int pos) { return (bool)(n & (1 << pos)); }
int d1[5005], n;
char s[5005], str[5005];
void manodd() {
  int l = 0, r = -1;
  for (int i = 0; i < n; ++i) {
    int k = (i > r ? 1 : min(d1[l + r - i], r - i));
    while (i + k < n && i - k >= 0 && s[i + k] == s[i - k]) ++k;
    d1[i] = k--;
    if (i + k > r) l = i - k, r = i + k;
  }
}
void make() {
  int k = 0;
  s[k++] = '$';
  for (int i = 0; i < n; i++) {
    s[k++] = '#';
    s[k++] = str[i];
  }
  s[k++] = '#';
  s[k] = 0;
  n = k;
}
struct info {
  int l, r;
  info() {}
  info(int ll, int rr) {
    l = ll;
    r = rr;
  }
  bool operator<(const info &p) const {
    if (l == p.l)
      return r < p.r;
    else
      return l < p.l;
  }
};
vector<info> v;
int F(int x, int l) {
  int low = l, high = v.size() - 1, mid, ans = -1;
  while (low <= high) {
    mid = (low + high) / 2;
    int my = v[mid].l;
    if (my > x) {
      ans = mid;
      high = mid - 1;
    } else
      low = mid + 1;
  }
  if (ans == -1) return 0;
  return v.size() - ans;
}
int main() {
  scanf("%s", str);
  n = strlen(str);
  make();
  manodd();
  int len = strlen(str);
  for (int i = 0; i < len; i++) {
    int my = d1[(i + 1) * 2];
    my /= 2;
    int l = i, r = i;
    for (int j = 0; j < my; j++) {
      v.push_back(info(l, r));
      l--;
      r++;
    }
    if (i) {
      int my = d1[(i + 1) * 2 - 1];
      my = (my - 1) / 2;
      int l = i - 1;
      int r = i;
      for (int j = 0; j < my; j++) {
        v.push_back(info(l, r));
        l--;
        r++;
      }
    }
  }
  sort(v.begin(), v.end());
  long long ret = 0;
  for (int i = 0; i < v.size(); i++) {
    ret += F(v[i].r, i);
  }
  printf("%lld", ret);
  printf("\n");
  return 0;
}

```