Một xâu được gọi là đối xứng, nếu nó đọc ngược cũng giống như đọc xuôi. Ví dụ các xâu "z", "aa", "abba", "madam" là đối xứng và các xâu "ab", "abc", "abab" là không đối xứng. Một xâu được gọi là đối xứng đôi, nếu nó được tạo thành bằng cách ghép hai xâu đối xứng có độ dài bằng nhau. Ví dụ các xâu "ab", "aabb", "aaaa" là đối xứng đôi và các xâu "aaa", "abba" và "aaaabb" là không đối xứng đôi.

Cho trước một xâu ~s~, bạn hãy viết một chương trình đếm xem có bao nhiêu xâu con của xâu ~s~ là đối xứng đôi. Nói cách khác, có bao nhiêu cặp ~(l,r)~ sao cho xâu con ~s_l s_{l+1}…s_r~ là đối xứng đôi. Ví dụ, xâu s= "abacac" có 6 xâu con đối xứng đôi là: "ab", "ba", "ac", "ca", "ac", "abacac".

Input dòng đầu tiên chứa số nguyên ~n~ với ~1≤n≤5 \times 10^5~ là độ dài xâu ~s~. Dòng thứ hai chứa xâu ~s~ bao gồm các chữ cái tiếng Anh viết thường.

Output số xâu con đối xứng đôi của xâu ~s~.

Sample input 1

6
abacac

Sample output 1

6

Sample input 2

1
e

Sample output 2

0

Ràng buộc:

• Có ~30\%~ số test của bài thỏa mãn: ~1≤n≤500;~
• Có ~30\%~ số test của bài thỏa mãn: ~1≤n≤5000;~
• Có ~40\%~ số test không có ràng buộc gì thêm.