Cho một chuỗi kí tự s, đếm xem có bao nhiều chuỗi con của s là chuỗi palindrome.

Chuỗi con của s là một chuỗi kí tự gồm các kí tự liên tiếp trong s.

Một chuỗi palindrome là một chuỗi đọc xuôi hay ngược đều như nhau vd: "aa", "aba", "abba" ..

Input

1 Dòng duy nhất chứa chuỗi s ~( 1<= s.length() <= 5000) ~

Kết quả

Số lượng chuỗi con của s là chuỗi palindrome.

Sample Input

aybabtutu

Sample Output

12

giải thích 12 => {"a", "y", "b", "a", "b", "t", "u", "t", "u", "bab", "tut", "utu"}