题目描述

$Bob$ 从商场买来一串长度为 $n$ 的黑白珍珠构成的链子，黑珍珠用 B 表示，白珍珠用 W 表示。

$Bob$ 可以从中间取出连续的一段做成手链，$Bob$ 要求做出的手链中黑白珍珠数量相同，$Bob$ 想知道他有多少种方法取出连续一段？ 取出的位置端点不同，就是不同的方法。（取出的手链至少长度为 $2$ ）

输入格式

第一行一个整数 $n$

第二行一个长度为 $n$ 的由 B 和 W 构成的字符串

输出格式

一个整数，表示方法数。

（方法数可能比较大，注意开 long long）

5
BWBWB

6

样例 1 解释

可以截取：[1,2],[1,4],[2,3],[2,5],[3,4],[4,5] 这 6 个区间，区间内黑白珍珠数量相同。

5
BBBBB

0

10
BBWWBWWBWW

10

数据规模与约定

$Subtask1$ : $2 \le n \le 100$ , $20$ 分

$Subtask2$ : $2 \le n \le 2000$ , $30$ 分

$Subtask3$ : $2 \le n \le 10^6$ , $50$ 分