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

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
long double min(long double a, long double b) {
  if (a < b)
    return a;
  else
    return b;
}
long double max(long double a, long double b) {
  if (a < b)
    return b;
  else
    return a;
}
long double min3(long double a, long double b, long double c) {
  return min(a, min(b, c));
}
long double max3(long double a, long double b, long double c) {
  return max(a, max(b, c));
}
long long ceil1(long double x, long double y) {
  long double q = x / y;
  if ((long long)q == q) return q;
  return q + 1;
}
long long NC = 100;
long long N = 1e9 + 7;
const long long S = 3e5 + 7;
long long mod(long long n);
long long gcd(long long a, long long b);
long long modM(long long n, long long m);
long long modA(long long n, long long m);
long long modS(long long n, long long m);
long long power(long long a, long long b);
void pra(long long a[], long long n);
void ipgraph(long long n, long long m);
vector<vector<long long>> v;
vector<bool> vis;
void solve() {
  string s;
  cin >> s;
  long long n = s.length();
  vector<long long> sum(n, 1), dp(n);
  vector<vector<long long>> pal(n, vector<long long>(n, 0));
  dp[0] = 0;
  for (long long i = 0; i < n; i++) pal[i][i] = 1;
  for (long long i = 1; i < n; i++) {
    for (long long j = 0; j < n; j++) {
      if (i + j >= n) break;
      if (s[j] == s[i + j]) {
        if (i == 1)
          pal[j][i + j] = 1;
        else
          pal[j][i + j] = pal[j + 1][i + j - 1];
        sum[i + j] += pal[j][i + j];
      }
    }
  }
  for (long long i = 1; i < n; i++) sum[i] += sum[i - 1];
  for (long long i = 1; i < n; i++) {
    dp[i] = dp[i - 1];
    for (long long j = 1; j < i + 1; j++) {
      dp[i] += pal[j][i] * sum[j - 1];
    }
  }
  cout << (dp[n - 1]) << '\n';
  ;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  cout << setprecision(15);
  long long t = 1;
  while (t--) solve();
  cerr << '\n'
       << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC
       << "ms\n";
  return 0;
}
void ipgraph(long long n, long long m) {
  v.assign(n, vector<long long>());
  vis.assign(n, 0);
  long long x, y;
  for (long long i = 0; i < m; i++) {
    cin >> x >> y;
    x--, y--;
    v[y].push_back(x);
    v[x].push_back(y);
  }
}
long long gcd(long long a, long long b) {
  if (b > a) return gcd(b, a);
  if (b == 0) return a;
  return gcd(b, a % b);
}
long long power(long long a, long long b) {
  if (b == 0) return 1;
  long long c = power(a, b / 2);
  if (b % 2 == 0)
    return modM(c, c);
  else
    return modM(modM(c, c), a);
}
void pra(long long a[], long long n) {
  for (long long i = 0; i < n; i++) cout << a[i] << " ";
  cout << '\n';
}
long long mod(long long n) { return (n % N + N) % N; }
long long modM(long long n, long long m) { return ((n % N * m % N) + N) % N; }
long long modA(long long n, long long m) { return ((n % N + m % N) + N) % N; }
long long modS(long long n, long long m) { return ((n % N - m % N) + N) % N; }