ith building is a restaurant.

As a city official, you would like to select 3 buildings for random inspection. However, to ensure variety, no two consecutive buildings out of the selected buildings can be of the same type.

For example, given s = "0 _**0**_ 1 _**1**_ 0 _**1**_ ", we cannot select the 1st, 3rd, and 5th buildings as that would form "0** _11_** " which is not allowed due to having two consecutive buildings of the same type.

Return thenumber of valid ways to select 3 buildings.

Examples

Example 1

Input: s = "001101"
Output: 6
Explanation: 
The following sets of indices selected are valid:
- [0,2

Related Tags