Duel#1851
Two duelists have chosen a dark alley as the venue for their duel. Along the alley, there are trees and bushes. The distance between adjacent objects is one meter. The duel is to be conducted with the following rules. A tree is chosen as the starting point. Then, two other trees that are equidistant from the starting point in opposite directions are marked as firing positions. The duelists start from the starting point and move in opposite directions. When the duelists reach the marked trees, they turn around and start shooting at each other.
A scheme representing the arrangement of trees along the alley is given. Determine the number of ways to choose a starting point and firing positions according to the rules of the duel.
The input contains a string consisting of the characters '0' and '1', representing the scheme of the alley. Trees are denoted by '1', and bushes by '0'. The length of the string does not exceed characters.
Output the number of ways to choose a starting point and firing positions according to the rules of the duel.
Example 1
In the first example, the possible duel configurations (the starting tree and firing trees are shown in bold): , 10\textbf{1}0\textbf{1}0\textbf{1}01, , and .