Cho xâu \(S\), đếm số palindrome con phân biệt trong xâu (hai palindrome con cùng nội dung tại vị trí khác nhau tính là một).

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

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

Định dạng đầu ra

• Một số nguyên là số palindrome con phân biệt.

Ví dụ

Input:

ababa

Output:

5

Ràng buộc

• 100% số điểm: \(|S| \le 2000\).