#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2020;
const unsigned long long BASE = 1e9 + 7;
unsigned long long powers[MAXN];
unsigned long long fhash[MAXN], bhash[MAXN];
char str[MAXN];
int N;
int endp[MAXN], startp[MAXN];
int main(int argc, char *argv[]) {
  scanf("%s", str);
  N = strlen(str);
  powers[0] = 1;
  for (int i = (1), _i = (N); i <= _i; ++i) {
    powers[i] = powers[i - 1] * BASE;
  }
  for (int i = (1), _i = (N); i <= _i; ++i) {
    fhash[i] = fhash[i - 1] + (str[i - 1] * powers[N - i]);
    bhash[N - i + 1] = bhash[N - i + 2] + (str[N - i] * powers[N - i]);
  }
  for (int i = 1; i <= N; i++) {
    for (int j = 1; j <= i; j++) {
      unsigned long long f = (fhash[i] - fhash[j - 1]) * powers[j - 1];
      unsigned long long b = (bhash[j] - bhash[i + 1]) * powers[N - i];
      if (f == b) {
        bool good = true;
        for (int k = j; k <= i; k++) {
          if (str[k - 1] != str[i - (k - j) - 1]) {
            good = false;
            break;
          }
        }
        if (good) {
          endp[i]++;
          startp[j]++;
        }
      }
    }
  }
  unsigned long long ans = 0;
  for (int i = 1; i <= N; i++) {
    for (int j = 1; j < i; j++) {
      ans += (unsigned long long)startp[i] * (unsigned long long)endp[j];
    }
  }
  cout << ans << "\n";
  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 = 2020;
const unsigned long long BASE = 1e9 + 7;
unsigned long long powers[MAXN];
unsigned long long fhash[MAXN], bhash[MAXN];
char str[MAXN];
int N;
int endp[MAXN], startp[MAXN];
int main(int argc, char *argv[]) {
  scanf("%s", str);
  N = strlen(str);
  powers[0] = 1;
  for (int i = (1), _i = (N); i <= _i; ++i) {
    powers[i] = powers[i - 1] * BASE;
  }
  for (int i = (1), _i = (N); i <= _i; ++i) {
    fhash[i] = fhash[i - 1] + (str[i - 1] * powers[N - i]);
    bhash[N - i + 1] = bhash[N - i + 2] + (str[N - i] * powers[N - i]);
  }
  for (int i = 1; i <= N; i++) {
    for (int j = 1; j <= i; j++) {
      unsigned long long f = (fhash[i] - fhash[j - 1]) * powers[j - 1];
      unsigned long long b = (bhash[j] - bhash[i + 1]) * powers[N - i];
      if (f == b) {
        bool good = true;
        for (int k = j; k <= i; k++) {
          if (str[k - 1] != str[i - (k - j) - 1]) {
            good = false;
            break;
          }
        }
        if (good) {
          endp[i]++;
          startp[j]++;
        }
      }
    }
  }
  unsigned long long ans = 0;
  for (int i = 1; i <= N; i++) {
    for (int j = 1; j < i; j++) {
      ans += (unsigned long long)startp[i] * (unsigned long long)endp[j];
    }
  }
  cout << ans << "\n";
  return 0;
}

```