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 CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 2005;
vector<pair<long long, long long> > v;
char str[maxn];
int n;
void init() {
  cin >> (str + 1);
  n = strlen(str + 1);
  for (int i = 1; i <= n; i++) {
    int l = i, r = i;
    while (l > 0 && r <= n && str[l] == str[r]) {
      v.push_back(make_pair(l, r));
      l--, r++;
    }
    l = i, r = i + 1;
    while (l > 0 && r <= n && str[l] == str[r]) {
      v.push_back(make_pair(l, r));
      l--, r++;
    }
  }
}
class element {
 public:
  int l, r;
  long long plus, val;
};
class Tree {
 public:
  element tree[maxn << 2];
  void build(int id, int l, int r) {
    tree[id].l = l;
    tree[id].r = r;
    tree[id].plus = 0;
    if (l == r) {
      tree[id].val = 0;
      return;
    }
    int mid = (l + r) / 2;
    build(id * 2, l, mid);
    build(id * 2 + 1, mid + 1, r);
    tree[id].val = tree[id * 2].val + tree[id * 2 + 1].val;
  }
  void add(int id, int l, int r, long long num) {
    if (tree[id].l >= l && tree[id].r <= r) {
      tree[id].plus += num;
      tree[id].val += num * (tree[id].r - tree[id].l + 1);
      return;
    }
    if (tree[id].l > r || tree[id].r < l) return;
    push_down(id);
    if (tree[id * 2].r >= l) add(id * 2, l, r, num);
    if (tree[id * 2 + 1].l <= r) add(id * 2 + 1, l, r, num);
    tree[id].val = tree[id * 2].val + tree[id * 2 + 1].val;
  }
  void push_down(int id) {
    if (tree[id].l != tree[id].r)
      for (int j = id * 2; j <= id * 2 + 1; j++) {
        tree[j].val += tree[id].plus * (tree[j].r - tree[j].l + 1);
        tree[j].plus += tree[id].plus;
      }
    tree[id].plus = 0;
  }
  long long query(int id, int l, int r) {
    if (tree[id].l >= l && tree[id].r <= r) return tree[id].val;
    if (tree[id].l > r || tree[id].r < l) return 0;
    long long s = 0;
    push_down(id);
    if (tree[id * 2].r >= l) s += query(id * 2, l, r);
    if (tree[id * 2 + 1].l <= r) s += query(id * 2 + 1, l, r);
    return s;
  }
} t;
void solve() {
  t.build(1, 0, n);
  sort(v.begin(), v.end());
  long long ans = 0;
  for (int i = 0; i < v.size(); i++) {
    ans += t.query(1, 0, v[i].first - 1);
    t.add(1, v[i].second, v[i].second, 1);
  }
  cout << ans << "\n";
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  init();
  solve();
  return 0;
}