Lớp học múa khiêu vũ dạ hội của giáo sư Padegras có ~n~ học sinh nam và nữ ghi tên. Giáo sư cho tất cả học sinh xếp thành một hàng dọc và chọn một nhóm các học sinh liên tiếp nhau cho buổi học đầu tiên với yêu cầu là số học sinh nam và nữ phải bằng nhau.

Hãy xác định, giáo sư Padegras có bao nhiêu cách lựa chọn khác nhau cho buổi học đầu tiên.

Input:

•Dòng đầu tiên chứa số nguyên ~n~ (~1 ≤ n ≤ 10^6~),

•Dòng thứ 2 chứa xâu độ dài ~n~ bao gồm các ký tự từ tập {~a, b~} xác định dòng xếp hàng, ~a~ là nam, ~b~ – nữ.

Output:

Một số nguyên – số cách lựa chọn.

Ví dụ

Input

8

abbababa

Output

13

Ràng buộc:

• 30% số test tương ứng với n ≤ 500

• 40% số test tiếp theo tương ứng với 500 < n ≤ 10000

• 30% số test cuối cùng tương ứng với 10000 < n ≤ ~10^6~