Xâu nhị phân cân bằng là một xâu khác rỗng, chỉ gồm các chữ số $0$ và $1$ và số lượng các chữ số $0$ bằng số lượng các chữ số $1$. Ví dụ: $10$, $01$, $1100$, $1001$, ... Một xâu khác rỗng được gọi là một xâu con của một xâu $S$ cho trước nếu nó là dãy ký tự liên tục trong $S$. Ví dụ: $S = 101$ thì các xâu $1$, $10$, $01$, $101$ là các xâu con của $S$.

Yêu cầu: Cho một xâu nhị phân $S$. Đếm số lượng xâu con nhị phân cân bằng của $S$.

Input

Đọc từ file văn bản BBIN.INP có cấu trúc như sau:

• Dòng thứ nhất chứa số nguyên dương $N$ là độ dài xâu nhị phân $S$;
• Dòng thứ hai chứa xâu nhị phân $S$.

Output

Ghi ra file văn bản BBIN.OUT gồm một dòng ghi một số là số xâu nhị phân cân bằng của $S$.

Scoring

• Subtask 1 ($40\%$): $N \leq 100$;
• Subtask 2 ($30\%$): $N \leq 5000$;
• Subtask 3 ($30\%$): $N \leq 10^6$.

Example

3
101

2

8
01101010

13