Một xâu ký tự được gọi là xâu đối xứng (Palindrome) nếu nó đọc từ trái sang phải hay từ phải sang trái đều giống hệt nhau (ví dụ: madam, racecar).

Ta định nghĩa rằng: Một xâu ký tự được gọi là xâu tiềm năng nếu ta có thể sắp xếp lại (hoán vị) các ký tự của nó để tạo thành một xâu đối xứng. Ví dụ, xâu aabcb là xâu tiềm năng vì có thể hoán vị thành bacab.

Yêu cầu: Cho một xâu \(S\) độ dài \(N\) chỉ gồm các chữ cái in thường tiếng Anh. Hãy đếm số lượng đoạn con liên tiếp của \(S\) là xâu tiềm năng.

Lưu ý: Hai chuỗi con có cùng giá trị nhưng nằm ở vị trí khác nhau được tính là hai đoạn con riêng biệt.

Input

• Một dòng duy nhất chứa xâu ký tự \(S\) (\(1 \leq N \leq 10^5\)).

Output

• In ra một số nguyên duy nhất là số lượng đoạn con liên tiếp của \(S\) thỏa mãn điều kiện.

Example

aabcb

8

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(N \leq 300\).
• Subtask \(2\) (\(20\%\) số điểm): \(N \leq 3000\).
• Subtask \(3\) (\(20\%\) số điểm): Xâu \(S\) chỉ gồm hai chữ cái a và b.
• Subtask \(4\) (\(40\%\) số điểm): Không có ràng buộc gì thêm.