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.OutputStream;
import java.io.PrintWriter;

import sun.util.logging.resources.logging;

public class Task159D {

	public static void main(String... args) throws NumberFormatException,
			IOException {
		Solution.main(System.in, System.out);
	}

	static class Scanner {

		private final BufferedReader br;
		private String[] cache;
		private int cacheIndex;

		Scanner(InputStream is) {
			br = new BufferedReader(new InputStreamReader(is));
			cache = new String[0];
			cacheIndex = 0;
		}

		int nextInt() throws IOException {
			if (cacheIndex >= cache.length) {
				cache = br.readLine().split(" ");
				cacheIndex = 0;
			}
			return Integer.parseInt(cache[cacheIndex++]);
		}

		String next() throws IOException {
			if (cacheIndex >= cache.length) {
				cache = br.readLine().split(" ");
				cacheIndex = 0;
			}
			return cache[cacheIndex++];
		}

		void close() throws IOException {
			br.close();
		}

	}

	static class Solution {

		public static void main(InputStream is, OutputStream os)
				throws NumberFormatException, IOException {
			PrintWriter pw = new PrintWriter(os);
			Scanner sc = new Scanner(is);

			String inp = sc.next();

			boolean isPalin[][] = new boolean[inp.length()][];
			for (int i = 0; i < inp.length(); i++) {
				isPalin[i] = new boolean[inp.length()];
			}

			// odd palindroms

			for (int i = 0; i < inp.length(); i++) {
				int r = 0;
				while (i - r >= 0 && i + r < inp.length()
						&& inp.charAt(i - r) == inp.charAt(i + r)) {
					isPalin[i - r][i + r] = true;
					r++;
				}
			}

			// even palindroms

			for (int i = 0; i + 1 < inp.length(); i++) {
				int r = 0;
				while (i - r >= 0 && i + 1 + r < inp.length()
						&& inp.charAt(i - r) == inp.charAt(i + 1 + r)) {
					isPalin[i - r][i + 1 + r] = true;
					r++;
				}
			}

			long retVal = 0;

			long palinEnds[] = new long[inp.length()];
			long palinBegins[] = new long[inp.length()];

			for (int a = 0; a < inp.length(); a++) {
				for (int b = a; b < inp.length(); b++) {
					if (isPalin[a][b]) {
						palinEnds[b]++;
					}
				}
			}

			for (int x = 0; x < inp.length(); x++) {
				for (int y = x; y < inp.length(); y++) {
					if (isPalin[x][y]) {
						palinBegins[x]++;
					}
				}
			}

			for (int b = 0; b < inp.length(); b++) {
				for (int x = b + 1; x < inp.length(); x++) {
					retVal += palinEnds[b] * palinBegins[x];
				}
			}

			pw.println(retVal);

			pw.flush();
			sc.close();
		}
	}

}