Cho xâu \(S\), hãy đếm số cặp vị trí \((i, j)\) với \(i < j\) sao cho xâu con \(S[i..j]\) là palindrome.

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

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

Định dạng đầu ra

• Một số nguyên là số cặp \((i, j)\).

Ví dụ

Input:

abc

Output:

3

Ràng buộc

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