#include <bits/stdc++.h>
using namespace std;
struct Hasher {
  string s;
  int n;
  vector<vector<long long> > hashes;
  vector<vector<long long> > revHashes;
  vector<vector<long long> > coefPows;
  Hasher(const string& s) {
    this->s = s;
    n = s.length();
  }
  void init(int coef) {
    vector<long long> hash(n);
    vector<long long> revHash(n);
    vector<long long> coefPow(n);
    coefPow[0] = 1;
    for (int i = 1; i < n; ++i) {
      coefPow[i] = coefPow[i - 1] * coef;
    }
    hash[0] = s[0] - 'a';
    for (int i = 1; i < n; ++i) {
      hash[i] = (s[i] - 'a') * coefPow[i] + hash[i - 1];
    }
    revHash[n - 1] = s[n - 1] - 'a';
    for (int i = n - 2; i >= 0; --i) {
      revHash[i] = (s[i] - 'a') * coefPow[n - i - 1] + revHash[i + 1];
    }
    hashes.push_back(hash);
    revHashes.push_back(revHash);
    coefPows.push_back(coefPow);
  }
  long long getHash(int from, int to, int coefIdx) {
    long long res = hashes[coefIdx][to];
    if (from) res -= hashes[coefIdx][from - 1];
    res *= coefPows[coefIdx][n - from - 1];
    return res;
  }
  long long getRevHash(int from, int to, int coefIdx) {
    long long res = revHashes[coefIdx][from];
    if (to != n - 1) res -= revHashes[coefIdx][to + 1];
    res *= coefPows[coefIdx][to];
    return res;
  }
  bool checkPalindrome(int from, int to) {
    for (int i = 0; i < hashes.size(); ++i) {
      if (getHash(from, to, i) != getRevHash(from, to, i)) {
        return false;
      }
    }
    return true;
  }
};
int main() {
  string str;
  cin >> str;
  Hasher hasher(str);
  hasher.init(31);
  hasher.init(33);
  int n = str.length();
  vector<long long> begins, ends;
  hasher.checkPalindrome(0, n - 1);
  for (int i = 0; i < n; ++i) {
    for (int j = i; j < n; ++j) {
      if (hasher.checkPalindrome(i, j)) {
        begins.push_back(i);
        ends.push_back(j);
      }
    }
  }
  long long res = 0;
  sort(begins.begin(), begins.end());
  for (int i = 0; i < ends.size(); ++i) {
    int lb =
        lower_bound(begins.begin(), begins.end(), ends[i] + 1) - begins.begin();
    long long dif = ends.size() - lb;
    res += dif;
  }
  cout << res << endl;
  return 0;
}

### Prompt

Please create a solution in cpp to 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;
struct Hasher {
  string s;
  int n;
  vector<vector<long long> > hashes;
  vector<vector<long long> > revHashes;
  vector<vector<long long> > coefPows;
  Hasher(const string& s) {
    this->s = s;
    n = s.length();
  }
  void init(int coef) {
    vector<long long> hash(n);
    vector<long long> revHash(n);
    vector<long long> coefPow(n);
    coefPow[0] = 1;
    for (int i = 1; i < n; ++i) {
      coefPow[i] = coefPow[i - 1] * coef;
    }
    hash[0] = s[0] - 'a';
    for (int i = 1; i < n; ++i) {
      hash[i] = (s[i] - 'a') * coefPow[i] + hash[i - 1];
    }
    revHash[n - 1] = s[n - 1] - 'a';
    for (int i = n - 2; i >= 0; --i) {
      revHash[i] = (s[i] - 'a') * coefPow[n - i - 1] + revHash[i + 1];
    }
    hashes.push_back(hash);
    revHashes.push_back(revHash);
    coefPows.push_back(coefPow);
  }
  long long getHash(int from, int to, int coefIdx) {
    long long res = hashes[coefIdx][to];
    if (from) res -= hashes[coefIdx][from - 1];
    res *= coefPows[coefIdx][n - from - 1];
    return res;
  }
  long long getRevHash(int from, int to, int coefIdx) {
    long long res = revHashes[coefIdx][from];
    if (to != n - 1) res -= revHashes[coefIdx][to + 1];
    res *= coefPows[coefIdx][to];
    return res;
  }
  bool checkPalindrome(int from, int to) {
    for (int i = 0; i < hashes.size(); ++i) {
      if (getHash(from, to, i) != getRevHash(from, to, i)) {
        return false;
      }
    }
    return true;
  }
};
int main() {
  string str;
  cin >> str;
  Hasher hasher(str);
  hasher.init(31);
  hasher.init(33);
  int n = str.length();
  vector<long long> begins, ends;
  hasher.checkPalindrome(0, n - 1);
  for (int i = 0; i < n; ++i) {
    for (int j = i; j < n; ++j) {
      if (hasher.checkPalindrome(i, j)) {
        begins.push_back(i);
        ends.push_back(j);
      }
    }
  }
  long long res = 0;
  sort(begins.begin(), begins.end());
  for (int i = 0; i < ends.size(); ++i) {
    int lb =
        lower_bound(begins.begin(), begins.end(), ends[i] + 1) - begins.begin();
    long long dif = ends.size() - lb;
    res += dif;
  }
  cout << res << endl;
  return 0;
}

```