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.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

/* by Skyly */

public class VKCup2012_Qual2_ProblemD {
    private void solve() throws IOException {
        char[] str = nextCharArray();
        int n = str.length;
        long[] L = new long[n + 1]; //[ , ]
        long[] R = new long[n + 1]; //[ , ]
        Arrays.fill(L, 0L);
        Arrays.fill(R, 0L);
        
        //odd-length palindromes
        for (int i = 0; i < n; ++i) {
            for (int j = 0; 0 <= i - j && i + j < n; ++j) {
                if (str[i - j] != str[i + j]) break;
                ++L[i + j];
                ++R[i - j];
            }
        }
        //even-length palindromes
        for (int i = 0; i < n - 1; ++i) {
            if (str[i] != str[i + 1]) continue;
            for (int j = 0; 0 <= i - j && i + 1 + j < n; ++j) {
                if (str[i - j] != str[i + 1 + j]) break;
                ++L[i + 1 + j];
                ++R[i - j];
            }
        }
        
        for (int i = 1; i < n; ++i) {
            L[i] += L[i - 1];
        }
                
        long ans = 0L;
        for (int i = 0; i < n; ++i) {
            ans += L[i] * R[i + 1];
        }
        writer.println(ans);
    }
    
    public static void main(String[] args) {
        new VKCup2012_Qual2_ProblemD().run();
    }

    BufferedReader reader;
    PrintWriter writer;
    StringTokenizer tokenizer;

    public void run() {
        try {
            //long startTime = System.currentTimeMillis();
            reader = new BufferedReader(new InputStreamReader(System.in));
            writer = new PrintWriter(System.out);
            tokenizer = null;
            solve();
            writer.flush();
            reader.close();
            writer.close();
            //System.err.println("Execution time: " + (System.currentTimeMillis() - startTime) + " ms");
        } catch (Exception e) {
            e.printStackTrace();
            System.exit(1);
        }
    }
    
    public int nextInt() throws IOException {
        return Integer.parseInt(nextToken());
    }
    public long nextLong() throws IOException {
        return Long.parseLong(nextToken());
    }
    public double nextDouble() throws IOException {
        return Double.parseDouble(nextToken());
    }
    public char[] nextCharArray() throws IOException {
        return nextToken().toCharArray();
    }
    public char nextChar() throws IOException {
        String buffer = nextToken();
        if (buffer.length() > 1) throw new IOException();
        return buffer.charAt(0);
    }
    public String nextToken() throws IOException {
        while (tokenizer == null || !tokenizer.hasMoreTokens()) {
            tokenizer = new StringTokenizer(reader.readLine());
        }
        return tokenizer.nextToken();
    }
    
}