Có 𝑛 bạn nam và bạn nữ đứng quanh một vòng tròn, các bạn được đánh số từ 1 tới 𝑛 theo chiều kim đồng hồ. Người ta muốn chọn một số bạn đứng liên tiếp trên vòng tròn sao cho số bạn được chọn > 0, đồng thời số bạn nam được chọn đúng bằng số bạn nữ được chọn.

Yêu cầu: Cho biết số cách chọn thỏa mãn điều kiện trên. (Hai cách chọn được coi là khác nhau nếu tồn tại một bạn được chọn trong một cách nhưng không được chọn trong cách còn lại).

Dữ liệu:

- Dòng 1 chứa số nguyên dương 𝑛 ≤ 10⁶
- Dòng 2 chứa 𝑛 ký tự. Ký tự thứ 𝑖 là dấu “+” (dấu cộng) nếu bạn thứ 𝑖 là bạn nam, là dấu “-” (dấu trừ) nếu bạn thứ 𝑖 là bạn nữ.

Kết quả:

Ghi ra một số nguyên duy nhất là số cách chọn tìm được