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 JAVA):

Solution:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.io.StreamTokenizer;

public class Main {
	static class Assert {
		static void check(boolean e) {
			if (!e) {
				throw new Error();
			}
		}
	}

	class Scanner {

		StreamTokenizer in;

		Scanner(InputStream is) {
			in = new StreamTokenizer(new BufferedReader(new InputStreamReader(is)));
			in.resetSyntax();
			in.whitespaceChars(0, 32);
			in.wordChars(33, 255);
		}

		String next() {
			try {
				in.nextToken();
				Assert.check(in.ttype == in.TT_WORD);
				return in.sval;
			} catch (IOException e) {
				throw new Error(e);
			}
		}

		int nextInt() {
			return Integer.parseInt(next());
		}
	}

	public static void main(String[] argv) {
		new Main().run();
	}

	void run() {
		in = new Scanner(System.in);
		out = new PrintWriter(System.out);
		try {
			solve();
		} finally {
			out.close();
		}
	}

	PrintWriter out;
	Scanner in;
	long cntPal(String s) {
		int n = s.length();
		int d1[] = new int[n];
		int l = 0, r = -1;
		for (int i = 0; i < n; ++i) {
			int k = (i > r ? 0 : Math.min(d1[l + r - i], r - i)) + 1;
			while (i + k < n && i - k >= 0 && s.charAt(i + k) == s.charAt(i - k))
				++k;
			d1[i] = --k;
			if (i + k > r) {
				l = i - k;
				r = i + k;
			}
		}
		int d2[] = new int[n];
		l = 0;
		r = -1;
		for (int i = 0; i < n; ++i) {
			int k = (i > r ? 0 : Math.min(d2[l + r - i + 1], r - i + 1)) + 1;
			while (i + k - 1 < n && i - k >= 0 && s.charAt(i + k - 1) == s.charAt(i - k))
				++k;
			d2[i] = --k;
			if (i + k - 1 > r) {
				l = i - k;
				r = i + k - 1;
			}
		}
		long res = 0;
		for (int i = 0; i < n; i++) {
			res += d1[i] + d2[i];
		}

		return res;
	}

	void fillPal(boolean[][] a, String s) {
		int n = s.length();
		for (int i = 0; i < n; i++)
			a[i][i] = true;
		for (int len = 2; len <= n; len++) {
			for (int i = 0; i + len - 1 < n; i++) {
				int j = i + len - 1;
				if ((s.charAt(i) == s.charAt(j) && ((len == 2) || (a[i + 1][j - 1])))) {
					a[i][j] = true;
				}
			}
		}
	}

	void solve() {
		String s = in.next();
		long d[] = new long[s.length()];
		for (int i = 0; i < s.length(); i++) {
			d[i] = cntPal(s.substring(0, i + 1)) + i + 1;
		}
		boolean isPal[][] = new boolean[s.length()][s.length()];
		fillPal(isPal, s);
		long res = 0;
		for (int i = 1; i < s.length(); i++) {
			for (int j = i; j < s.length(); j++) {
				if (isPal[i][j]) {
					res += d[i - 1];
				}
			}
		}
		out.println(res);

	}
}