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$", $\ldots$

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 xâu $S$.
Yêu cầu: cho một xâu nhị phân $S$, đếm xem trong $S$ có bao nhiêu xâu con nhị phân cân bằng?

Input:

• Dòng đầu tiên gồm một số nguyên dương $N$ là độ dài của xâu nhị phân $S$.
• Dòng thứ hai là xâu nhị phân $S$.

Output:

• Gồm một dòng là số xâu con nhị phân cân bằng của $S$.

Subtasks:

• Subtask $1$ ($40$%): $0 < n \leq 100$
• Subtask $2$ ($30$%): $100 < n \leq 5000$
• Subtask $3$ ($30$%): $5000 < n \leq 10^{6}$

Example

3
101

2

8
01101010

13