Lớp học múa khiêu vũ dạ hội của thầy Nam có ~n~ học sinh nam và nữ ghi tên. Thầy giáo cho tất cả học sinh xếp thành một hàng, sau đó thầy 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 giúp thầy Nam đếm xem có bao nhiêu cách lựa chọn khác nhau cho buổi học đầu tiên.

Dữ liệu

• Dòng đầu tiên chứa số nguyên ~n~ (~1 \le n \le 10^6~).
• Dòng thứ hai là một xâu gồm ~n~ kí tự liên tiếp, thể hiện giới tính và vị trí xếp hàng của các bạn (a là nam, b là nữ).

Kết quả

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

Ví dụ

DANCE.INP

8
abbababa

DANCE.OUT

13

Giới hạn

• ~1 \le n \le 10^6~.