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.*;
import java.util.*;

public class Palin {
	public static void main(String[] args) {
		new Palin().run();
	}

	BufferedReader br;
	StringTokenizer st;
	PrintWriter out;
	boolean eof = false;
	Random rand = new Random(12345);

	private void run() {
		Locale.setDefault(Locale.US);
		try {
			br = new BufferedReader(new InputStreamReader(System.in));
			out = new PrintWriter(System.out);
			solve();
			out.close();
		} catch (Throwable e) {
			e.printStackTrace();
			System.exit(566);
		}
	}

	String nextToken() {
		while (st == null || !st.hasMoreTokens()) {
			try {
				st = new StringTokenizer(br.readLine());
			} catch (Exception e) {
				eof = true;
				return "0";
			}
		}
		return st.nextToken();
	}

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

	long nextLong() {
		return Long.parseLong(nextToken());
	}

	double nextDouble() {
		return Double.parseDouble(nextToken());
	}

	private void solve() throws IOException {
		char[] s = nextToken().toCharArray();
		int[] len = new int[2 * s.length - 1];
		for (int i = 0; i < s.length; i++) {
			len[2 * i] = 1;
			while (0 <= i - len[2 * i] && i + len[2 * i] < s.length
					&& s[i - len[2 * i]] == s[i + len[2 * i]]) {
				len[2 * i]++;
			}
		}
		for (int i = 0; i + 1 < s.length; i++) {
			len[2 * i + 1] = 0;
			while (0 <= i - len[2 * i + 1] && i + 1 + len[2 * i + 1] < s.length
					&& s[i - len[2 * i + 1]] == s[i + 1 + len[2 * i + 1]]) {
				len[2 * i + 1]++;
			}
		}
		long ans = 0;
		for (int i = 0; i < len.length; i++) {
			long len1 = len[i];
			for (int j = i + 1; j < len.length; j++) {
				long len2 = len[j];
				long c = (j - i) / 2;
				if (i % 2 == 0 || j % 2 == 0) {
					c++;
				}
				long y = Math.min(len1, Math.max(0, c - len2));
				ans += y * len2;
				long z = Math.min(len2, c - y);
				long w = Math.min(y + z, len1);
				if (w > y) {
					ans += (z + y) * (w - y) - w * (w + 1) / 2 + y * (y + 1)
							/ 2;
				}
			}
		}
		out.println(ans);
	}
}