An muốn đếm số lượng xâu con palindrome trong xâu \(S\) (kể cả palindrome độ dài 1). Hai xâu con ở vị trí khác nhau được tính là khác nhau. Hãy dùng Manacher để đếm nhanh.

Định dạng đầu vào

• Một dòng chứa xâu \(S\) (\(1 \le |S| \le 10^5\)).

Định dạng đầu ra

• In ra tổng số xâu con palindrome.

Ví dụ

Input:

abac

Output:

5

Giải thích: Các palindrome: a (vị trí 0), b (vị trí 1), a (vị trí 2), c (vị trí 3), aba.

Ràng buộc

• 50% số điểm: \(|S| \le 1000\).
• 50% số điểm còn lại: \(|S| \le 10^5\).