C. Game with Binary String

Consider the following game. Two players have a binary string (a string consisting of characters 0 and/or 1). The players take turns, the first player makes the first turn. During a player's turn, he or she has to choose exactly two adjacent elements of the string and remove them (the first element and the last element are also considered adjacent). Furthermore, there are additional constraints depending on who makes the move:

• if it's the first player's move, both chosen characters should be 0;
• if it's the second player's move, at least one of the chosen characters should be 1.

The player who can't make a valid move loses the game. This also means that if the string currently has less than characters, the current player loses the game.

You are given a binary string of length . You have to calculate the number of its substrings such that, if the game is played on that substring and both players make optimal decisions, the first player wins. In other words, calculate the number of pairs such that and the first player has a winning strategy on the string .

The first line contains one integer ( ).

The second line contains the string , consisting of exactly characters. Each character of the string is either 0 or 1.

Print one integer — the number of substrings such that, if the game is played on that substring, the first player wins.

输入 #1

10
0010010011

输出 #1

12

In the first example, the following substrings are winning for the first player ( denotes ):

• ;
• ;
• ;
• ;
• ;
• ;
• ;
• ;
• ;
• ;
• ;
• .