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 Main {
    int start[ ], end[ ], len;
    char ch[ ];
    public void solve( ) throws Throwable {
        ch = in.next( ).toCharArray( );
        len = ch.length;
        start = new int[ len ];
        end = new int[ len ];
        for ( int i = 0; i < len; ++i ) {
            add( i, i );
            add( i, i + 1 );
        }
        for ( int i = 1; i < len; ++i ) {
            end[ i ] += end[ i - 1 ];
        }
        long ans = 0;
        for ( int i = len - 1; i > 0; --i ) {
            ans += ( long )start[ i ] * end[ i - 1 ];
        }
        out.println( ans );
    }

    void add( int l, int r ) {
        for ( ; l >= 0 && r < len && ch[ l ] == ch[ r ]; --l, ++r ) {
            ++start[ l ];
            ++end[ r ];
        }
    }

    public void run( ) {
        in = new FastScanner( System.in );
        out = new PrintWriter( new PrintStream( System.out ), true );

        try {
            solve( );
            out.close( );
            System.exit( 0 );
        } catch( Throwable e ) {
            e.printStackTrace( );
            System.exit( -1 ); 
        }
    }


    public void debug( Object...os ) {
        System.err.println( Arrays.deepToString( os ) );
    }

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



    private FastScanner in;
    private PrintWriter out;

    private static class FastScanner {
        private int charsRead;
        private int currentRead;
        private byte buffer[ ] = new byte[ 0x1000 ];
        private InputStream reader;

        public FastScanner( InputStream in ) {
            reader = in;
        }

        public int read( ) {
            if ( charsRead == -1 ) {
                throw  new InputMismatchException( );
            }

            if ( currentRead >= charsRead ) {
                currentRead = 0;
                try {
                    charsRead = reader.read( buffer );

                } catch( IOException e ) {
                    throw new InputMismatchException(  );
                }

                if ( charsRead <= 0 ) {
                    return -1;
                }
            }

            return buffer[ currentRead++ ];
        }

        public int nextInt( ) {
            int c = read( );

            while ( isWhitespace( c ) ) {
                c = read( );
            }

            if ( c == -1 ) {
                throw new NullPointerException( );
            } 

            if ( c != '-' && !( c >= '0' && c <= '9' ) ) {
                throw new InputMismatchException( );
            }

            int sign = c == '-' ? -1 : 1;
            if ( sign == -1 ) {
                c = read( );
            }

            if ( c == -1 || !( c >= '0' && c <= '9' ) ) {
                throw new InputMismatchException( );
            }

            int ans = 0;
            while ( !isWhitespace( c )  && c != -1 ) {
                if ( !( c >= '0' && c <= '9' ) ) {
                    throw  new InputMismatchException( );
                }
                int num = c - '0';
                ans = ans * 10 + num;
                c = read( );
            }

            return ans * sign;
        }

        public long nextLong( ) {
            int c = read( );

            while ( isWhitespace( c ) ) {
                c = read( );
            }

            if ( c == -1 ) {
                throw new NullPointerException( );
            }

            if ( c != '-' && !( c >= '0' && c <= '9' ) ) {
                throw new InputMismatchException( );
            }

            int sign = c == '-' ? -1 : 1;
            if ( sign == -1 ) {
                c = read( );
            }

            if ( c == -1 || !( c >= '0' && c <= '9' ) ) {
                throw new InputMismatchException( );
            }

            long ans = 0;
            while ( !isWhitespace( c )  && c != -1 ) {
                if ( !( c >= '0' && c <= '9' ) ) {
                    throw  new InputMismatchException( );
                }
                int num = c - '0';
                ans = ans * 10 + num;
                c = read( );
            }

            return ans * sign;
        }



        public boolean isWhitespace( int c ) {
            return  c == ' ' || c == '\t' || c == '\n' || c == '\r' || c == -1;
        }

        public String next( ) {
            int c = read( );
            StringBuffer ans = new StringBuffer( );

            while ( isWhitespace( c ) && c != -1 ) {
                c  = read( );
            }

            if ( c == -1 ) {
                return null;
            }

            while ( !isWhitespace( c ) && c != -1 ) {
                ans.appendCodePoint( c );
                c = read( );
            }

            return ans.toString( );

        }

               
        public String nextLine( ) {
            String ans = nextLine0( );

            while ( ans.trim( ).length( ) == 0 ) {
                ans = nextLine0( );
            }

            return ans;
        }
        
        private String nextLine0( ) {
            int c = read( );
            if ( c == -1 ) {
                return null;
            }
            StringBuffer ans = new StringBuffer( );
            while ( c != '\n' && c != '\r' && c != -1 ) {
                ans.appendCodePoint( c );
                c = read( );
            }

            return ans.toString( );

        }


       
        public double nextDouble( ) {
            int c = read( );
            while ( isWhitespace( c ) ) {
                c = read( );
            }

            if ( c == -1 ) {
                throw new NullPointerException( ); 
            }

            if ( c != '.' && c != '-' && !( c >= '0' && c <= '9' ) ) {
                throw new InputMismatchException( );
            }

            int sign = c == '-' ? -1 : 1;
            if ( c == '-' ) {
                c = read( );
            }
            double ans = 0;
            while ( c != -1 && c != '.' && !isWhitespace( c ) ) {
                if ( !( c >= '0' && c <= '9' ) ) {
                    throw new InputMismatchException( );
                }

                int num = c - '0'; 
                ans = ans * 10.0 + num;
                c = read( );
            }

            if ( !isWhitespace( c ) && c != -1 && c != '.' ) {
                throw new InputMismatchException( );
            }

            double pow10 = 1.0;

            if ( c == '.' ) {
                c = read( );
            }

            while ( !isWhitespace( c ) && c != -1 ) {
                pow10 *= 10.0;

                if ( !( c >= '0' && c <= '9' ) ) {
                    throw new InputMismatchException( );
                }
                int num = c - '0';
                ans = ans * 10.0 + num; 
                c = read( );
            }

            return ans * sign / pow10;
        }
    }

}