#include <bits/stdc++.h>
using namespace std;
const int maxn = 2000 + 10;
vector<pair<long long, long long> > l, pal;
string s;
bool mark[maxn][maxn];
long long ans;
bool is_pal(int l, int r) { return mark[l + 1][r - 1] & s[l - 1] == s[r - 1]; }
int main() {
  ios_base::sync_with_stdio(0);
  cin >> s;
  if ((int)s.size() < 2) {
    cout << 0 << endl;
    exit(0);
  }
  for (int i = 1; i <= (int)s.size(); i++) {
    mark[i][i] = true;
    pal.push_back(pair<long long, long long>(i, i));
    l.push_back(pair<long long, long long>(i, 0));
  }
  for (int i = 1; i < (int)s.size(); i++) {
    mark[i][i + 1] = (s[i - 1] == s[i]);
    if (mark[i][i + 1]) {
      pal.push_back(pair<long long, long long>(i, i + 1));
      l.push_back(pair<long long, long long>(i, 0));
    }
  }
  for (int len = 3; len <= (int)s.size(); len++)
    for (int pos = 1; pos <= ((int)s.size() - len + 1); pos++) {
      mark[pos][pos + len - 1] = is_pal(pos, pos + len - 1);
      if (mark[pos][pos + len - 1]) {
        pal.push_back(pair<long long, long long>(pos, pos + len - 1));
        l.push_back(pair<long long, long long>(pos, 0));
      }
    }
  sort(l.begin(), l.end());
  l.push_back(pair<long long, long long>(9999999, 0));
  for (int i = 0; i < (int)l.size(); i++) {
    l[i].second = i + 1;
  }
  for (int i = 0; i < (int)pal.size(); i++) {
    pair<long long, long long> tmp =
        *upper_bound(l.begin(), l.end(),
                     pair<long long, long long>(pal[i].second, 99999999));
    if (tmp.second != l.back().second) ans += ((int)l.size() - tmp.second);
  }
  cout << ans << endl;
  return 0;
}

### 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;
const int maxn = 2000 + 10;
vector<pair<long long, long long> > l, pal;
string s;
bool mark[maxn][maxn];
long long ans;
bool is_pal(int l, int r) { return mark[l + 1][r - 1] & s[l - 1] == s[r - 1]; }
int main() {
  ios_base::sync_with_stdio(0);
  cin >> s;
  if ((int)s.size() < 2) {
    cout << 0 << endl;
    exit(0);
  }
  for (int i = 1; i <= (int)s.size(); i++) {
    mark[i][i] = true;
    pal.push_back(pair<long long, long long>(i, i));
    l.push_back(pair<long long, long long>(i, 0));
  }
  for (int i = 1; i < (int)s.size(); i++) {
    mark[i][i + 1] = (s[i - 1] == s[i]);
    if (mark[i][i + 1]) {
      pal.push_back(pair<long long, long long>(i, i + 1));
      l.push_back(pair<long long, long long>(i, 0));
    }
  }
  for (int len = 3; len <= (int)s.size(); len++)
    for (int pos = 1; pos <= ((int)s.size() - len + 1); pos++) {
      mark[pos][pos + len - 1] = is_pal(pos, pos + len - 1);
      if (mark[pos][pos + len - 1]) {
        pal.push_back(pair<long long, long long>(pos, pos + len - 1));
        l.push_back(pair<long long, long long>(pos, 0));
      }
    }
  sort(l.begin(), l.end());
  l.push_back(pair<long long, long long>(9999999, 0));
  for (int i = 0; i < (int)l.size(); i++) {
    l[i].second = i + 1;
  }
  for (int i = 0; i < (int)pal.size(); i++) {
    pair<long long, long long> tmp =
        *upper_bound(l.begin(), l.end(),
                     pair<long long, long long>(pal[i].second, 99999999));
    if (tmp.second != l.back().second) ans += ((int)l.size() - tmp.second);
  }
  cout << ans << endl;
  return 0;
}

```