THPT Chuyên Bến Tre

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 1 số nhóm 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 chứa số nguyên dương n (1<=n<=10^6).

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

Output

- Một dòng duy nhất là số cách lựa chọn.

Example

Input:
8

abbababa
Output:
13