#include <bits/stdc++.h>
using namespace std;
long long gcd(long long a, long long b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
string toBin(long long a) {
  string res = "";
  while (a) {
    res += char((a & 1) + '0');
    a >>= 1;
  }
  reverse(res.begin(), res.end());
  return res;
}
const long long mod = 1e18;
long long expo(long long base, long long pow) {
  long long ans = 1;
  while (pow != 0) {
    if (pow & 1 == 1) {
      ans = ans * base;
      ans = ans % mod;
    }
    base *= base;
    base %= mod;
    pow /= 2;
  }
  return ans;
}
long long inv(long long x) { return expo(x, mod - 2); }
bool isPal(string ss) {
  int len = ss.length();
  for (int i = 0; i < len / 2; i++) {
    int comp = len - i - 1;
    if (ss[i] != ss[comp]) return false;
  }
  return true;
}
double pi = 3.141592653589793238462643;
double error = 0.0000001;
const int M = 100001;
string str;
bool check(int l, int r) {
  int len = r - l + 1;
  string hh = str.substr(l, len);
  return isPal(hh);
}
vector<pair<int, int> > vec;
long long sum[2222];
int pal[2222][2222];
long long dp[2222];
int main() {
  cin >> str;
  sum[0] = 1;
  for (int i = 1; i < str.length(); i++) {
    sum[i] = sum[i - 1];
    for (int j = 0; j <= i; j++) {
      if (check(j, i)) {
        pal[j][i] = 1;
        sum[i]++;
      }
    }
  }
  for (int i = 1; i < str.length(); i++) {
    dp[i] = dp[i - 1];
    for (int j = 1; j <= i; j++) {
      dp[i] += (sum[j - 1] * pal[j][i]);
    }
  }
  cout << dp[str.size() - 1];
}

### Prompt

In cpp, your task is to solve 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;
long long gcd(long long a, long long b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
string toBin(long long a) {
  string res = "";
  while (a) {
    res += char((a & 1) + '0');
    a >>= 1;
  }
  reverse(res.begin(), res.end());
  return res;
}
const long long mod = 1e18;
long long expo(long long base, long long pow) {
  long long ans = 1;
  while (pow != 0) {
    if (pow & 1 == 1) {
      ans = ans * base;
      ans = ans % mod;
    }
    base *= base;
    base %= mod;
    pow /= 2;
  }
  return ans;
}
long long inv(long long x) { return expo(x, mod - 2); }
bool isPal(string ss) {
  int len = ss.length();
  for (int i = 0; i < len / 2; i++) {
    int comp = len - i - 1;
    if (ss[i] != ss[comp]) return false;
  }
  return true;
}
double pi = 3.141592653589793238462643;
double error = 0.0000001;
const int M = 100001;
string str;
bool check(int l, int r) {
  int len = r - l + 1;
  string hh = str.substr(l, len);
  return isPal(hh);
}
vector<pair<int, int> > vec;
long long sum[2222];
int pal[2222][2222];
long long dp[2222];
int main() {
  cin >> str;
  sum[0] = 1;
  for (int i = 1; i < str.length(); i++) {
    sum[i] = sum[i - 1];
    for (int j = 0; j <= i; j++) {
      if (check(j, i)) {
        pal[j][i] = 1;
        sum[i]++;
      }
    }
  }
  for (int i = 1; i < str.length(); i++) {
    dp[i] = dp[i - 1];
    for (int j = 1; j <= i; j++) {
      dp[i] += (sum[j - 1] * pal[j][i]);
    }
  }
  cout << dp[str.size() - 1];
}

```