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.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Random;
import java.util.StringTokenizer;

public class Main implements Runnable {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		(new Thread(new Main())).start();
	}

	StringTokenizer st;
	BufferedReader in;
	PrintWriter out;

	public void run() {
		try {
			in = new BufferedReader(new InputStreamReader(System.in));
			// in = new BufferedReader(new FileReader("input"));
			out = new PrintWriter(System.out);
			solve();
		} catch (Exception e) {
			e.printStackTrace();
		} finally {
			out.flush();
			out.close();
		}
	}

	String nextToken() throws IOException {
		while (st == null || !st.hasMoreTokens())
			st = new StringTokenizer(in.readLine());
		return st.nextToken();
	}

	int nextInt() throws NumberFormatException, IOException {
		return Integer.parseInt(nextToken());
	}

	long nextLong() throws NumberFormatException, IOException {
		return Long.parseLong(nextToken());
	}

	class Pair implements Comparable<Pair> {

		public Pair(int pos, boolean start) {
			this.pos = pos;
			this.start = start;
		}

		public int getPos() {
			return pos;
		}

		public boolean isStart() {
			return start;
		}

		@Override
		public int compareTo(Pair o) {
			if (pos == o.pos) {
				if (start == o.start)
					return 0;
				return start ? -1 : 1;
			}
			return pos - o.pos;
		}

		@Override
		public String toString() {
			return "Event: @" + pos + " " + (start ? "start" : "end");
		}

		private int pos;
		private boolean start;
	}

	private long MAGIC = 51;
	private long mod = (long) 1e9 + 7;

	void printArr(long[] arr, String title) {
		out.println(title);
		for (long l : arr) {
			out.print(l + " ");
		}
		out.println();
	}

	int[] preCalc = new int[(int) 3e3];

	long bpow(long x, int n) {
		if (preCalc[0] == 0) {
			preCalc[0] = 1;
			for (int i = 1; i < preCalc.length; i++) {
				preCalc[i] = (int) ((preCalc[i - 1] * x) % mod);
			}
		}
		return preCalc[n];
	}

	boolean isPolyndrome(String x) {
		String p = "";
		for (int i = 0; i < x.length(); i++) {
			p = x.charAt(i) + p;
		}
		return x.equals(p);
	}

	int[] mh1, mh2;

	void gen(String str, int Pos) {
		for (int i = 0; i <= str.length(); i++) {
			mh1[i] = mh2[i] = 0;
		}
		long[] hh = { 0, 0 };
		int n = str.length();

		mh2[n] = 0;
		for (int i = 0; i < n; i++) {
			int[] id = { i, n - i - 1 };
			int[][] mass = { mh1, mh2 };
			for (int j = 0; j < id.length; j++) {
				long cur = str.charAt(id[j]) - 'a' + 1;
				hh[j] = (hh[j] * MAGIC + cur) % mod;
				mass[j][id[j]] = (int) hh[j];
			}
		}
		//
		// printArr(mh1, "h1");
		// printArr(mh2, "h2");
		//
		for (int i = 0; i <= str.length() / 2; i++) {
			int endPos[] = { 2 * i, 2 * i + 1 }, startPos[] = { i, i + 1 };
			long hashLeft = mh1[i], hashRight = 0;

			for (int j = 0; j < endPos.length; j++) {
				if (endPos[j] >= n)
					continue;

				long leftSum = (mh2[endPos[j] + 1] * bpow(MAGIC, (i + 1)))
						% mod;
				hashRight = (mh2[startPos[j]] - leftSum + mod) % mod;

				// String subst = str.substring(0, endPos[j] + 1);
				if (hashLeft == hashRight) {
					if (EVENTS) {
						events.add(new Pair(Pos, true));
						events.add(new Pair(Pos + endPos[j], false));
					} else {
						events1.add(Pos);
						events2.add(Pos + endPos[j]);
					}
				}
			}
		}

	}

	boolean EVENTS = false;

	ArrayList<Pair> events = new ArrayList<Pair>();
	ArrayList<Integer> events1 = new ArrayList<Integer>();
	ArrayList<Integer> events2 = new ArrayList<Integer>();

	long calc(String s) {
		events.clear();
		events2.clear();
		mh1 = new int[s.length() + 1];
		mh2 = new int[s.length() + 1];

		for (int i = 0; i < s.length(); i++) {
			gen(s.substring(i), i);
		}
		Collections.sort(events);
		Collections.sort(events2);
		long ans = 0;
		long ended = 0;
		if (EVENTS) {
			for (Pair event : events) {
				// out.println(event);
				if (!event.isStart()) {
					ended++;
				} else {
					ans += ended;
				}
			}
		} else {
			int id = 0;
			for (Integer event : events1) {
				int cur_time = event;
				while (id < events2.size() && events2.get(id) < cur_time) {
					ended++;
					id++;
				}

				ans += ended;
			}
		}
		return ans;
	}

	long calcStupid(String s) {
		int n = s.length();
		long arr[] = new long[n + 1];
		long arr2[] = new long[n + 1];
		long res = 0;
		for (int i = 0; i < n; i++) {
			for (int j = i; j < n; j++) {
				String s1 = s.substring(i, j + 1);
				if (isPolyndrome(s1)) {
					arr[i]++;
				}
			}
		}
		for (int i = n; i > 0; i--) {
			arr2[i - 1] = arr2[i] + arr[i - 1];
		}

		for (int i = 0; i < n; i++) {
			for (int j = i; j < n; j++) {
				String s1 = s.substring(i, j + 1);
				if (isPolyndrome(s1)) {
					res += arr2[j + 1];
				}
			}
		}

		return res;
	}

	void test() {
		Random r = new Random();
		StringBuilder s = new StringBuilder();
		for (int i = 0; i < (int) 1e5; i++) {
			int len = 2000;// r.nextInt((int) 2000) + 1;
			s = new StringBuilder();
			for (int j = 0; j < len; j++) {
				s.append((char) (r.nextInt(26) + 'a'));
			}

			long a1 = calc(s.toString());
			long a2 = a1;// ;
			if (a1 != a2) {
				out.println(s.toString());
			} else {
				out.print(a1 + " ");
				out.flush();
				out.println(calcStupid(s.toString()));
				out.flush();
			}
		}
	}

	void solve() throws Exception {
		String a = nextToken();
		// StringBuilder a = new StringBuilder();
		// for (int i = 0; i < 2000; i++)
		// a.append('a');
		// out.println(a)
		out.println(calc(a));
	}

}