建筑美学

题目描述

在一个新兴城市的规划蓝图中，有一条笔直的街道，街道两旁预定建造 $n$ 栋建筑。由于经费限制，每栋建筑只能在两种风格中选择其一：办公楼（用 '0' 表示）或 餐厅（用 '1' 表示）。

当前街道的建筑方案可以用一个长度为 $n$ 的二进制字符串 $s$ 来表示，其中 $s_i$ 表示第 $i$ 栋建筑的类型。

市长希望从这 $n$ 栋建筑中随机选择 3 栋不同的建筑进行“美学评估”。然而，为了保证视觉上的多样性，选出来的 3 栋建筑必须满足一个条件：相邻选中的两栋建筑不能是同一种类型。

例如，如果你选出的 3 栋建筑类型（按街道顺序排列）是 "010" 或者 "101"，则是符合美学要求的；而 "001" 或 "110" 则不符合要求。

请你计算，在这个给定的建筑方案 $s$ 中，一共有多少种不同的选择方案（选择 3 栋建筑的下标 $(i, j, k)$ 且 $0 \le i < j < k < n$），使得选出的建筑序列符合美学要求？

输入格式

输入一个长度为 $n$ 的二进制字符串 $s$，由 '0' 和 '1' 组成。

输出格式

输出一个整数，表示符合要求的选择方案总数。

输入输出样例 #1

输入 #1

001101

输出 #1

6

样例 1 说明

符合要求的下标组合有：

• (0, 2, 4) -> "010"
• (0, 3, 4) -> "010"
• (1, 2, 4) -> "010"
• (1, 3, 4) -> "010"
• (2, 4, 5) -> "101"
• (3, 4, 5) -> "101" 共 6 种。

输入输出样例 #2

输入 #2

11100

输出 #2

0

数据范围

对于 $60\%$ 的数据，$3 \le n \le 1000$。

对于 $100\%$ 的数据，$3 \le n \le 10^5$。 注意：结果可能较大，请使用合适的数据类型（如 C++ 中的 long long）。