Cho một chuỗi ~s~ gồm ~n~ ký tự. Nhiệm vụ của bạn là đếm số lượng chuỗi con đối xứng (hay còn gọi là chuỗi palindrome) trong chuỗi này. Một chuỗi con đối xứng là chuỗi mà nếu đọc từ trái sang phải và từ phải sang trái đều giống nhau. Hãy khám phá chuỗi này và tìm ra những chuỗi con đối xứng ẩn giấu bên trong.

Giới hạn

• ~1 ≤ n ≤ 200~
• ~s~ chỉ bao gồm các ký tự chữ cái Latin viết thường.

Đầu vào

• Dòng đầu tiên: chuỗi ~s~

Đầu ra

• Một số nguyên duy nhất: số lượng chuỗi con đối xứng trong ~s~.

Sample Input

ababa

Sample Output

9

Giải thích

Trong chuỗi "ababa", các chuỗi con đối xứng là:

• Ký tự đơn lẻ: a, b, a, b, a (5 chuỗi).
• Chuỗi dài hơn: aba, bab, aba, ababa (4 chuỗi).
• Tổng cộng, số lượng chuỗi con đối xứng là 9.