~Copium~ rất mê cái đẹp, anh ta không những mê gái mà còn mê cả xâu. Một xâu ~Copium~ cho là đẹp nếu nó tồn tại một cách sắp xếp sao cho xâu đó là một palindrome. Một hôm một người bạn của anh ta đưa cho anh một xâu ~S~, và với tính tò mò của mình, ~Copium~ đã dành hàng tiếng để đếm số xâu con ~[l, r]~ ~(1 \le l \le r \le n)~ của xâu ~S~ sao cho nó là một xâu đẹp. Nhưng vì xâu ~S~ quá dài nên ~Copium~ đang cần bạn giúp!

Một xâu palindrome được định nghĩa là xâu khi đọc từ trái sang phải và ngược lại đều có kết quả như nhau.

Input

• Dòng đầu gồm một số nguyên ~n~ là chiều dài của xâu ~S~ ~(1 \le n \le 10^5)~
• Dòng thứ hai là xâu ~S~ có chiều dài ~n~ chỉ gồm các ký tự từ ~[a, z]~ viết thường và các số thuộc ~[0, 9]~

Output

• In ra một số duy nhất là số xâu con đẹp trong xâu ~S~.

Sample Input 1

5
abacc

Sample Output 1

9

Sample Input 2

5
bedao

Sample Output 2

5

Subtask

• ~10\%~ số test thoả mãn xâu ~S~ chỉ gồm ~2~ ký tự 'a' và 'b'
• ~30\%~ số test tiếp theo có ~n \le 2 \times 10^3~
• ~60\%~ số test còn lại không có điều kiện gì thêm