Рассмотрим следующую игру. У двух игроков есть двоичная строка (строка, состоящая из символов 0 и/или 1). Игроки ходят по очереди, первый игрок делает первый ход. Во время хода игрок должен выбрать ровно два соседних элемента строки и удалить их (первый элемент и последний элемент также считаются соседними). Более того, существуют дополнительные ограничения в зависимости от того, кто делает ход:

• если ход делает первый игрок, оба выбранных символа должны быть 0;
• если ход делает второй игрок, по крайней мере один из выбранных символов должен быть 1.

Игрок, который не может сделать ход, проигрывает игру. Это также означает, что если в строке в данный момент меньше $$$2$$$ символов, текущий игрок проигрывает игру.

Вам дана двоичная строка $$$s$$$ длины $$$n$$$. Вам нужно вычислить количество ее таких подстрок, что если игра будет сыграна на этой подстроке и оба игрока будут играть оптимально, первый игрок выиграет. Другими словами, вычислите количество пар $$$(l, r)$$$ таких, что $$$1 \le l \le r \le n$$$ и у первого игрока есть выигрышная стратегия на строке $$$s_l s_{l+1} \dots s_r$$$.