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:
// Author: Victor Tarnavsky
// Date: 09.03.12

import java.util.*;

public class Pairs {
    
    private String str;

    public Pairs(String str) {
        this.str = str;
    }

    public static void main (String [] args) {
        String str = new Scanner(System.in).nextLine();
//        while(true) {
        Pairs pairs = new Pairs(str);
        pairs.createWords(str);
        System.out.println(pairs.countPairs());
  //      }
    }

    static class Word {
        int start;
        int end;

        Word(int start, int end) {
            this.start = start;
            this.end = end;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;

            Word word = (Word) o;

            if (end != word.end) return false;
            if (start != word.start) return false;

            return true;
        }

        @Override
        public int hashCode() {
            int result = start;
            result = 31 * result + end;
            return result;
        }
    }

    private void createWords (String str) {
        ArrayList<Word> words = new ArrayList<Word>();
        char [] strArray = str.toCharArray();
        
        for (int i = 0; i < strArray.length; i++) {
            for (int j = 0; i - j >= 0 && i + j < strArray.length; j++) {
                if (strArray[i - j] == strArray[i + j]) words.add(new Word(i - j, i + j));
                else break;
            }
            for (int j = 0; i - j >= 0 && i + j + 1 < strArray.length; j++) {
                if (strArray[i - j] == strArray[i + j + 1]) words.add(new Word(i - j, i + j + 1));
                else break;
            }
        }
        
        /*for (int i = 1; i <= strArray.length; i++) {
            //char [] cache = new char[i];

            for (int j = 0; ; j++) {
            
*//*            for (int j = 0; j <= strArray.length - i; j++) {
                //cache = 
                boolean palindrome = true;
                for (int k = 0; k < i/2; k++) {
                    if (strArray[j + k] != strArray[j + (i-1) - k]) {
                        palindrome = false;
                        break;
                    }
                }
                if (palindrome) words.add(new Word(j, j + i - 1));
            }*//*
        }*/
        Word [] array = words.toArray(new Word[words.size()]);
        Arrays.sort(array, startComparator);
        
        wordsSortedStart = array.clone();
        Arrays.sort(array, endComparator);
        wordsSortedEnd = array;
        wordsNumber = array.length;
    }
    
    private long countPairs () {
        long count = 0;

        int currentCross = 0;

        int startPointer = 0;
        int endPointer = 0;

        for (int i = 0; i < wordsNumber; i++) {
            while (endPointer < wordsNumber && wordsSortedEnd[endPointer].end == i - 1) {
                count += currentCross - 1;
                currentCross--;
                endPointer++;
            }

            while (startPointer < wordsNumber && wordsSortedStart[startPointer].start == i) {
                currentCross++;
                startPointer += 1;
            }

        }
        
        
        
        
        
        
        
        
        
        
        /*for (int i = 0; i < wordsNumber; i++) {

            Word current = wordsSortedStart[i];
            
            
            
            
            
            *//*int pos = Arrays.binarySearch(wordsSortedStart, current, startComparator);
            if (pos < 0) throw new RuntimeException("wow");
            HashSet<Word> set = new HashSet<Word>();
            while (pos > 0 && wordsSortedStart[pos-1].start == current.start) pos--;
            while (pos < wordsNumber && wordsSortedStart[pos].start <= current.end) {
                set.add(wordsSortedStart[pos]);
                pos++;
            }
            
            pos = Arrays.binarySearch(wordsSortedEnd, current, endComparator);
            while (pos < wordsNumber - 1 && wordsSortedEnd[pos+1].end == current.end) pos++;
            if (pos < 0) throw new RuntimeException("wow");
            while (pos >= 0 && wordsSortedEnd[pos].end >= current.start) {
                set.add(wordsSortedEnd[pos]);
                pos--;
            }*//*



            *//*count += (wordsNumber - set.size());*//*

            *//*for (int j = 0; j < wordsNumber; j++) {
                if (wordsSortedStart[j].start > current.end || wordsSortedStart[j].end < current.start) count++;
            }*//*

        }*/
        return wordsNumber*(wordsNumber - 1)/2 - count;
    }

    Comparator<Word> startComparator = new StartComparator();
    Comparator<Word> endComparator = new EndComparator();

    static class StartComparator implements Comparator<Word> {
        public int compare(Word o1, Word o2) {
            return o1.start - o2.start;
        }
    }

    static class EndComparator implements Comparator<Word> {
        public int compare(Word o1, Word o2) {
            return o1.end - o2.end;
        }
    }

    
    private Word [] wordsSortedStart;
    private Word [] wordsSortedEnd;
    private long wordsNumber;

    
    












    public static boolean isPalindrome (String str) {
        
        return new StringBuilder(str).reverse().toString().equals(str);
    }
}