#include <bits/stdc++.h>
using namespace std;
inline void pisz(int n) { printf("%d\n", n); }
template <typename T, typename TT>
ostream &operator<<(ostream &s, pair<T, TT> t) {
  return s << "(" << t.first << "," << t.second << ")";
}
template <typename T>
ostream &operator<<(ostream &s, vector<T> t) {
  for (int(i) = 0; (i) < (((int)(t.size()))); ++(i)) s << t[i] << " ";
  return s;
}
template <typename T, typename Aug>
struct AugTreap {
  struct Node {
    T v;
    int pr;
    Node *le, *ri;
    Aug al, ag;
  };
  Node *root;
  AugTreap() : root(0) {}
  inline static void recalc(Node *&n) {
    Aug left = n->le ? n->le->ag + n->al : n->al;
    n->ag = n->ri ? left + n->ri->ag : left;
  }
  inline void rotle(Node *&n) {
    Node *syn = n->le;
    n->le = syn->ri;
    syn->ri = n;
    n = syn;
    recalc(n->ri);
    recalc(n);
  }
  inline void rotri(Node *&n) {
    Node *syn = n->ri;
    n->ri = syn->le;
    syn->le = n;
    n = syn;
    recalc(n->le);
    recalc(n);
  }
  void insert_aux(Node *&n, const T &x, const Aug &aug) {
    if (!n) {
      n = new Node;
      n->v = x;
      n->pr = rand();
      n->le = n->ri = 0;
      n->al = n->ag = aug;
    } else if (x < n->v) {
      insert_aux(n->le, x, aug);
      if (n->pr > n->le->pr)
        rotle(n);
      else
        recalc(n);
    } else if (x > n->v) {
      insert_aux(n->ri, x, aug);
      if (n->pr > n->ri->pr)
        rotri(n);
      else
        recalc(n);
    } else {
      n->al = aug;
      recalc(n);
    }
  }
  void insert(const T &x, const Aug &aug) { insert_aux(root, x, aug); }
  Aug sumgeq_aux(const T &x, Node *n) {
    if (!n) return Aug();
    if (x > n->v) return sumgeq_aux(x, n->ri);
    if (x < n->v) {
      Aug left = sumgeq_aux(x, n->le) + n->al;
      return n->ri ? left + n->ri->ag : left;
    }
    return n->ri ? n->al + n->ri->ag : n->al;
  }
  Aug sumgeq(const T &x) { return sumgeq_aux(x, root); }
};
vector<int> manacher(string s, bool p) {
  int n = ((int)(s.size()));
  vector<int> res(n);
  int l = 0, r = -1;
  for (int(i) = 0; (i) < (n); ++(i)) {
    int k;
    if (i > r)
      k = 1;
    else
      k = min(res[l + r - i + p], r - i + p) + 1;
    while (i + k - p < n && i - k >= 0 && s[i + k - p] == s[i - k]) ++k;
    res[i] = --k;
    if (i + k - p > r) {
      l = i - k;
      r = i + k - p;
    }
  }
  return res;
}
char s[2048];
long long u[2048], ups[2048], ile1[2048], ile2[2048];
int main() {
  scanf("%s", s);
  int n = strlen(s);
  vector<int> p = manacher(s, 1), r = manacher(s, 0);
  u[n - 1] = 1;
  AugTreap<pair<int, int>, int> tr1, tr2;
  for (int(i) = (n - 1); (i) >= (0); --i) {
    tr1.insert(make_pair(-(i - r[i]), i), 1);
    ile1[i] = tr1.sumgeq(make_pair(-i, -5));
    ile2[i] = tr2.sumgeq(make_pair(-i, -5));
    tr2.insert(make_pair(-(i - p[i]), i), 1);
  }
  for (int(k) = (n - 2); (k) >= (0); --k) {
    u[k] = u[k + 1];
    u[k] += ile1[k];
    u[k] += ile2[k];
  }
  ups[0] = u[0];
  for (int(i) = (1); (i) <= (n - 1); ++i) ups[i] = ups[i - 1] + u[i];
  ups[n] = ups[n - 1];
  long long res = 0;
  for (int(x) = (0); (x) <= (n - 1); ++x) {
    res += ups[x + r[x] + 1] - ups[x];
    res += ups[x + p[x]] - ups[x];
  }
  cout << res << endl;
}

### Prompt

Please provide a Cpp coded solution 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;
inline void pisz(int n) { printf("%d\n", n); }
template <typename T, typename TT>
ostream &operator<<(ostream &s, pair<T, TT> t) {
  return s << "(" << t.first << "," << t.second << ")";
}
template <typename T>
ostream &operator<<(ostream &s, vector<T> t) {
  for (int(i) = 0; (i) < (((int)(t.size()))); ++(i)) s << t[i] << " ";
  return s;
}
template <typename T, typename Aug>
struct AugTreap {
  struct Node {
    T v;
    int pr;
    Node *le, *ri;
    Aug al, ag;
  };
  Node *root;
  AugTreap() : root(0) {}
  inline static void recalc(Node *&n) {
    Aug left = n->le ? n->le->ag + n->al : n->al;
    n->ag = n->ri ? left + n->ri->ag : left;
  }
  inline void rotle(Node *&n) {
    Node *syn = n->le;
    n->le = syn->ri;
    syn->ri = n;
    n = syn;
    recalc(n->ri);
    recalc(n);
  }
  inline void rotri(Node *&n) {
    Node *syn = n->ri;
    n->ri = syn->le;
    syn->le = n;
    n = syn;
    recalc(n->le);
    recalc(n);
  }
  void insert_aux(Node *&n, const T &x, const Aug &aug) {
    if (!n) {
      n = new Node;
      n->v = x;
      n->pr = rand();
      n->le = n->ri = 0;
      n->al = n->ag = aug;
    } else if (x < n->v) {
      insert_aux(n->le, x, aug);
      if (n->pr > n->le->pr)
        rotle(n);
      else
        recalc(n);
    } else if (x > n->v) {
      insert_aux(n->ri, x, aug);
      if (n->pr > n->ri->pr)
        rotri(n);
      else
        recalc(n);
    } else {
      n->al = aug;
      recalc(n);
    }
  }
  void insert(const T &x, const Aug &aug) { insert_aux(root, x, aug); }
  Aug sumgeq_aux(const T &x, Node *n) {
    if (!n) return Aug();
    if (x > n->v) return sumgeq_aux(x, n->ri);
    if (x < n->v) {
      Aug left = sumgeq_aux(x, n->le) + n->al;
      return n->ri ? left + n->ri->ag : left;
    }
    return n->ri ? n->al + n->ri->ag : n->al;
  }
  Aug sumgeq(const T &x) { return sumgeq_aux(x, root); }
};
vector<int> manacher(string s, bool p) {
  int n = ((int)(s.size()));
  vector<int> res(n);
  int l = 0, r = -1;
  for (int(i) = 0; (i) < (n); ++(i)) {
    int k;
    if (i > r)
      k = 1;
    else
      k = min(res[l + r - i + p], r - i + p) + 1;
    while (i + k - p < n && i - k >= 0 && s[i + k - p] == s[i - k]) ++k;
    res[i] = --k;
    if (i + k - p > r) {
      l = i - k;
      r = i + k - p;
    }
  }
  return res;
}
char s[2048];
long long u[2048], ups[2048], ile1[2048], ile2[2048];
int main() {
  scanf("%s", s);
  int n = strlen(s);
  vector<int> p = manacher(s, 1), r = manacher(s, 0);
  u[n - 1] = 1;
  AugTreap<pair<int, int>, int> tr1, tr2;
  for (int(i) = (n - 1); (i) >= (0); --i) {
    tr1.insert(make_pair(-(i - r[i]), i), 1);
    ile1[i] = tr1.sumgeq(make_pair(-i, -5));
    ile2[i] = tr2.sumgeq(make_pair(-i, -5));
    tr2.insert(make_pair(-(i - p[i]), i), 1);
  }
  for (int(k) = (n - 2); (k) >= (0); --k) {
    u[k] = u[k + 1];
    u[k] += ile1[k];
    u[k] += ile2[k];
  }
  ups[0] = u[0];
  for (int(i) = (1); (i) <= (n - 1); ++i) ups[i] = ups[i - 1] + u[i];
  ups[n] = ups[n - 1];
  long long res = 0;
  for (int(x) = (0); (x) <= (n - 1); ++x) {
    res += ups[x + r[x] + 1] - ups[x];
    res += ups[x + p[x]] - ups[x];
  }
  cout << res << endl;
}

```