#1431. [L1-8] 川川串串

川川最喜欢数串串了！很多人都说她有这个怪癖。不过，在她参加完 CCCC-GPLT 比赛后，穿越到了另一个世界，进行了一场奇妙的旅途。

在那个世界里，字符串仅由 '$\text a$' , '$\text c$' , '$\text m$' 三种字符构成，我们称之为 “串串”。

假如说有一个串串 $S$，长度为 $n$，满足：$1 \leq n \leq 10^6$。若串串 $S$ 被称为 “川串”，当且仅当：

1.“串串” $S$ 中必须含有 '$\text c$'；

2.对于任意 $S_i = \text c$，满足 $\sum_{j=1}^i [S_j=\text{m}] = 0$ 并且 $\sum_{j=i+1}^n [S_j=\text{a}] = 0$；

即：对于含有 $\text c$ 的 “串串” $S$ 中的每一个 '$\text c$'，它的前面没有 '$\text m$'，它的后面没有 '$\text a$'。

川川想知道，在一个 “串串” $S$ 的子串中，有多少个 “川串”。

子串：字符串中任意个连续的字符组成的子序列称为该串的子串，例如 $\text{aa}$ 的子串有：$\text{aa}$，$\text a$，$\text a$，$\varnothing$（空串）。

第一行输入一个正整数 $n$，表示 “串串” 的长度。

第二行输入一个长度为 $n$ 的 “串串”，它仅由 '$\text a$' , '$\text c$' , '$\text m$' 三种字符构成。

一行，一个正整数，表示 “川串” 的个数。

样例输入：

6
acccmm

样例输出：

17

样例解释：

该 “串串” 中，有以下子串为 “川串”：

$\text{ac}$，$\text{acc}$，$\text{accc}$，$\text{acccm}$，$\text{acccmm}$；

$\text c$，$\text{cc}$，$\text{ccc}$，$\text{cccm}$，$\text{cccmm}$；

$\text c$，$\text{cc}$，$\text{ccm}$，$\text{ccmm}$；

$\text c$，$\text{cm}$，$\text{cmm}$；

共有 $17$ 个 “川串”。

对于 $20\%$ 的数据，满足： $1 \leq n \leq 20$

对于另外 $30\%$ 的数据，满足： $1 \leq n \leq 100$

对于另外 $20\%$ 的数据，满足：$1 \leq n \leq 5000$

对于所有数据，满足： $1 \leq n \leq 10^6$； $S$ 仅由 '$\text a$' , '$\text c$' , '$\text m$' 三种字符构成。