Question
Equal Substrings
You are given a binary string KaTeX can only parse string typed expression consisting only of characters KaTeX can only parse string typed expression and KaTeX can only parse string typed expression. Your task is to count the number of substrings in which the number of occurrences of the substring KaTeX can only parse string typed expression is equal to the number of occurrences of the substring KaTeX can only parse string typed expression.
A substring is a contiguous part of the string.
Input
The first line contains a single integer KaTeX can only parse string typed expression — the length of the string.
The second line contains a binary string KaTeX can only parse string typed expression of length KaTeX can only parse string typed expression.
The second line contains a binary string KaTeX can only parse string typed expression of length KaTeX can only parse string typed expression.
Output
Print a single integer — the number of substrings such that the number of occurrences of KaTeX can only parse string typed expression is equal to the number of occurrences of KaTeX can only parse string typed expression.
Example
Input
5
01010
Output
9
Explanation
The valid substrings are:
"0"
"1"
"0"
"1"
"0"
"010"
"101"
"010"
"01010"
In each of these substrings, the number of occurrences of KaTeX can only parse string typed expression and KaTeX can only parse string typed expression is equal.
5
01010
Output
9
Explanation
The valid substrings are:
"0"
"1"
"0"
"1"
"0"
"010"
"101"
"010"
"01010"
In each of these substrings, the number of occurrences of KaTeX can only parse string typed expression and KaTeX can only parse string typed expression is equal.