题目描述

小珅在夏季运动会中赢得了冠军！不过这次领奖规则发生了改变，组委会给冠军准备了若干个水果排成一排，其中水果的种类只有两类：香蕉和苹果。

小珅只能拿走相邻若干个水果，必须拿走至少 3 个水果，且拿走的水果之中某一种类的水果有且只有一个。小珅非常聪明，知道选择哪一个区间内的水果可以拿到更多的水果，但是小珅并满足不于此，他还想知道在不破坏规则的情况下一共有多少种挑选水果的方法（只要起点和终点不完全相同就认为是不同的挑选方法）。

输入格式

一行，一个只包含字符 0 和 1 的字符串 s，其中字符 0 表示香蕉，字符 1 表示苹果。

输出格式

一行，一个整数表示结果。

样例输入

10101

样例输出

3

提示

样例 1 解释，可以挑选的方案有：

第 1∼3 个水果，即 101，其中只包含一个香蕉；

第 2∼4 个水果，即 010，其中只包含一个苹果；

第 3∼5 个水果，即 101，其中只包含一个香蕉。

可以证明再没有其他符合要求的挑选方案，因此一共有 3 种挑选方案。

数据范围

对于 40% 的数据保证：$3\le |s|\le 300$。

另外 80% 的数据保证：$3\le |s|\le 5000$。

对于 100% 的数据保证：$1\le |s|\le 5\times 10^{5}$，其中 $|s|$ 表示字符串 s 的长度，且字符串 s 中只包含字符 0 和 1 。

10101

3

1110000110100111010101000011010000000011011111110000100101101001100001010100000100110001110001110110000011111001001111011111001010100110001101100001000100111111110000101110011100101101100001110100111110101000000010011110001110101011010000101001011000111110110010100111000101100110101010010101001000010011011100111011100010011000110001101110110010001100011110000100001101111000100111000010011101101000111101000001111100110111001011101110010010110011110111011110101101110010011100111000100111110010111100111000110010001001000101100001100010101110101111101110001111000100001110001101001001111110011000010001011101101000000100011111111011001101110010010000110001110101110011010111001010100011110010000000010100101111010110100010101011100000100000000001110101111101000101110010000011101000000100010001110001101010100001111011010110000001010110000010011011011000101011100000001011011001110000100000101000110001010111101111001010101100010001100010010101101010011011101110100010000100011010110011111011001100101110011101010100000010111111000001001001010011001110000010000100100100110011101011111000000111100110110000011001110000101001000101101110110101101001011001011101001110101101101011001101001010011000000010001111000010010111101111010001101100101111000000110011111001001011010000100000000100010111010100110110011000100100010100100001010001100100100000111110101001011000101011111100110011010101111101000110110000100100110101101100100001001001101000101101111000110111000100010110011011110100000000010011100000011010011001010100110010111100001101011101011000000001000101001101110100101110000001001000111001111101000011011001011110111100001111011011100110001110010111101110101100111110010010001110100101000111000011010010110111100100110111000100010110111110111000010101100000011110100110001111110011010010011001110001111110011101111001011111110000011011101010101011101000101111011110

3788

1000101001011011100001111011001000111010100111010111010100011100111110001001111111000110100110000000011010110011001011011000111001110010111011101010011111101011010010100010001011011101111001001101010111010100100010100000000110010001000111111001110101011000100000101110010110111101110100000010100011000001000000101010011011111110001011000100111111101100101100111010110110101101000010110011001000100011001000100000100000111000101000001000010001001110010100000100101000000110110101110000001001111110100010111101111100101001100010000000000101110000101011100111001101001101000110011110000011111111011011010110110111000001000000000011001101101100101111010101010011011110110100011001110011010001101010011111100011010000110001111011100001000000100010100011110010100001110100010111101111111000100111000001101010000101001001010001001110001000110111101101111100000101101011000011011001011001001110011010101011110000100000101000111100011001001000010001110111001111010111010111100001001011001111110111011001010110101000111100000011100101101010111010110100111011110100100110110010001001110010101100001110100011011100110101011101010001011001011110010010000000010100110110111011110010010000000110111010010100110100011101000111101111000110010101011110101000111110000100100001001001001111100000011101001110100001011010100110001011011010001001100111000001111111110010111110010110101011111110110001010110011110111010100001100000101000011101001000000000100111111101000010111111110010100111100011110100011010011001100101110001011110001000001010100010011111010000000001011101010001111100011100111010110101010101010000001101100100101111110111011011001110010101110111011101100101000111000101101001100001001001111100011001000001011100110001011000111100101100000101010110000000110010111011011000101001100011111010110000101001111111101111110110111110001101101011100111011000111000010001010010111001100111111011010111001001101111100010010101111000010001001001001100010110000110100110101001101010110100010100110101100100010001100101010110011101001101101111010111111011010011011001000110111110111100110000001110101001011100010110111110001001011100101100000100011001101100100001101101110110000101100110101000100011011010111100000100101001000111100011011101100101010000110010111100011100010011111001001001110100111001110111011010011001001010000001010110100010110111110100000001111111011110000100000100010100110011011100110100011000110001000100100101100001101000011110101000001010100100011011011001011000110001100110100100011001100110000101000000011110110010011110101000110111111110001010010100100111000001111100100100000011010010101010110010101110110101000110011001001011011001000010010110001111000001010000010110011011100010101110100000111000110100000000011110001100100001000101010110110100111010110101111101101111101000011100011000000101101111000011010100001100001100001100001001110111111001110101110111100100001001100001111111101001011010001101110001101011000011011111000000001011000010011101011010100101100111010001101100000100111011011110001100001110011000111000100010100001110001100101010100100001110111010011110100111110101100011101000000000110000111111000011001011110000100011101110111001001010110011111000111101111010000000110000110011100100000000011110100000000010011101111010100111101100101101101001011001101101001000100110001010101110011001001111110110110000010100101000101110000100110110111111101110110011010001111000010001001111100111110000001110100000111000011111111000101111111010011001001101100101011101000011101101001011001101101110001001000111001101110001101101100010011100011111010011

7180