#include <bits/stdc++.h>
using namespace std;
double EPS = 1e-9;
int INF = 2000000000;
long long INFF = 8000000000000000000LL;
double PI = acos(-1);
inline string IntToString(int a) {
  char x[100];
  sprintf(x, "%d", a);
  string s = x;
  return s;
}
inline int StringToInt(string a) {
  char x[100];
  int res;
  strcpy(x, a.c_str());
  sscanf(x, "%d", &res);
  return res;
}
inline string GetString(void) {
  char x[1000005];
  scanf("%s", x);
  string s = x;
  return s;
}
inline bool angka(char a) { return (a >= '0' && a <= '9'); }
inline bool kecil(char a) { return (a >= 'a' && a <= 'z'); }
inline bool besar(char a) { return (a >= 'A' && a <= 'Z'); }
inline string uppercase(string s) {
  int n = (int)s.size();
  for (int(i) = (0); (i) < (n); (i)++)
    if (kecil(s[i])) s[i] = s[i] - 'a' + 'A';
  return s;
}
inline string lowercase(string s) {
  int n = (int)s.size();
  for (int(i) = (0); (i) < (n); (i)++)
    if (besar(s[i])) s[i] = s[i] - 'A' + 'a';
  return s;
}
string s;
bool palin[2005][2005];
int ada[2005], n;
long long jum[2005];
long long ans = 0;
int main() {
  s = GetString();
  n = (int)s.size();
  memset(palin, 0, sizeof(palin));
  for (int(i) = (0); (i) < (n); (i)++) palin[i][i] = 1;
  for (int(i) = (0); (i) < (n - 1); (i)++)
    if (s[i] == s[i + 1]) palin[i][i + 1] = 1;
  for (int(dif) = (3); (dif) <= (n); (dif)++)
    for (int(i) = (0); (i) <= (n - dif + 1); (i)++)
      palin[i][i + dif - 1] =
          (palin[i + 1][i + dif - 2] && (s[i] == s[i + dif - 1]));
  for (int(i) = (0); (i) < (n); (i)++)
    for (int(j) = (i); (j) < (n); (j)++)
      if (palin[i][j]) ++ada[i];
  jum[0] = ada[0];
  for (int(i) = (1); (i) < (n); (i)++) jum[i] = jum[i - 1] + (long long)ada[i];
  for (int(i) = (0); (i) < (n - 1); (i)++)
    for (int(j) = (i); (j) < (n - 1); (j)++)
      if (palin[i][j]) ans += (long long)(jum[n - 1] - jum[j]);
  cout << ans << endl;
  return 0;
}

### Prompt

Your challenge is to write a cpp solution 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;
double EPS = 1e-9;
int INF = 2000000000;
long long INFF = 8000000000000000000LL;
double PI = acos(-1);
inline string IntToString(int a) {
  char x[100];
  sprintf(x, "%d", a);
  string s = x;
  return s;
}
inline int StringToInt(string a) {
  char x[100];
  int res;
  strcpy(x, a.c_str());
  sscanf(x, "%d", &res);
  return res;
}
inline string GetString(void) {
  char x[1000005];
  scanf("%s", x);
  string s = x;
  return s;
}
inline bool angka(char a) { return (a >= '0' && a <= '9'); }
inline bool kecil(char a) { return (a >= 'a' && a <= 'z'); }
inline bool besar(char a) { return (a >= 'A' && a <= 'Z'); }
inline string uppercase(string s) {
  int n = (int)s.size();
  for (int(i) = (0); (i) < (n); (i)++)
    if (kecil(s[i])) s[i] = s[i] - 'a' + 'A';
  return s;
}
inline string lowercase(string s) {
  int n = (int)s.size();
  for (int(i) = (0); (i) < (n); (i)++)
    if (besar(s[i])) s[i] = s[i] - 'A' + 'a';
  return s;
}
string s;
bool palin[2005][2005];
int ada[2005], n;
long long jum[2005];
long long ans = 0;
int main() {
  s = GetString();
  n = (int)s.size();
  memset(palin, 0, sizeof(palin));
  for (int(i) = (0); (i) < (n); (i)++) palin[i][i] = 1;
  for (int(i) = (0); (i) < (n - 1); (i)++)
    if (s[i] == s[i + 1]) palin[i][i + 1] = 1;
  for (int(dif) = (3); (dif) <= (n); (dif)++)
    for (int(i) = (0); (i) <= (n - dif + 1); (i)++)
      palin[i][i + dif - 1] =
          (palin[i + 1][i + dif - 2] && (s[i] == s[i + dif - 1]));
  for (int(i) = (0); (i) < (n); (i)++)
    for (int(j) = (i); (j) < (n); (j)++)
      if (palin[i][j]) ++ada[i];
  jum[0] = ada[0];
  for (int(i) = (1); (i) < (n); (i)++) jum[i] = jum[i - 1] + (long long)ada[i];
  for (int(i) = (0); (i) < (n - 1); (i)++)
    for (int(j) = (i); (j) < (n - 1); (j)++)
      if (palin[i][j]) ans += (long long)(jum[n - 1] - jum[j]);
  cout << ans << endl;
  return 0;
}

```