题目描述

小蓝发现了一种奇特的生物，它的遗传信息可以表示为一个长度为 $n$ 的 $01$ 串 $s = s_0s_1 \cdots s_{n-1}$，其中的任意一段子串 $s_{l, r} = s_l s_{l+1} \cdots s_r$ 则可以构成一个基因。

我们称遗传信息的某两个位置相反，是指这两个位置上的字符不相同（即其中一个为 0，另一个为 1）。

小蓝想知道，有多少对不相交的相同长度的基因正好相反，即有多少对 $[(a, b), (c, d)]$ 满足 $0 \leq a \leq b < c \leq d < n$ 且子串 $s_{a, b}$ 和子串 $s_{c, d}$ 的每个位置恰好相反。

输入格式

输入一行包含一个长度为 $n$ 的 $01$ 串 $s$。

输出格式

输出一行包含一个整数表示答案。

10011

8

提示

样例说明

有以下 $8$ 对子串满足条件：$[(0,0),(1,1)]$、$[(0,0),(2,2)]$、$[(1,1),(3,3)]$、$[(1,1),(4,4)]$、$[(2,2),(3,3)]$、$[(2,2),(4,4)]$、$[(0,1),(2,3)]$、$[(1,2),(3,4)]$。

评测用例规模与约定

• 对于 $30\%$ 的评测用例，$1 \leq n \leq 20$；
• 对于所有评测用例，$1 \leq n \leq 1000$。