(dance_hn.*)

Lớp học múa khiêu vũ dạ hội của giáo sư Lê 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.

Yêu cầu: Tính số cách lựa chọn khác nhau cho buổi học đầu tiên của giáo sư Lê. Hai cách chọn được gọi là khác nhau nếu có ít nhất một bạn ở trong cách này mà không có trong cách khác.

Dữ liệu vào:

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

Kết quả:

• Ghi một số nguyên duy nhất là số cách lựa chọn khác nhau của giáo sư Lê.

Ví dụ:

Giải thích: trong ví dụ trên, giáo sư Lê có 13 cách lựa chọn nhóm các bạn cho buổi học đầu tiên: 1..2; 1..4; 1..6; 1..8; 3..4; 3..6; 3..8; 4..5; 4..7; 5..6; 5..8; 6..7; 7..8.

Ràng buộc:

+ 20% số test đầu tiên có \(n \leq 100\)

+ 30% số test tiếp theo có \(n \leq 10^{3}\)

+ 50% số test cuối: Không có ràng buộc gì thêm.