Đối xứng đôi

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}\dots 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".

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên dương $n$ ($1\le n\le 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.

Dữ liệu ra

In ra một số nguyên là số xâu con đối xứng đôi của xâu $s$.

Ràng buộc

• $1\le n\le 5\times {10}^5$.
• $s$ gồm $n$ chữ cái tiếng Anh viết thường.

Subtasks

Điểm được tính theo từng test.

• Subtask 1 ($30\%$ số test): $1\le n\le 500$.
• Subtask 2 ($30\%$ số test): $1\le n\le 5000$.
• Subtask 3 ($40\%$ số test): không có ràng buộc gì thêm.

Ví dụ