题目描述

给定一个长度为 $N$ 的序列 $A=(A_1,A_2,\\dots,A_N)$，其中每个元素都是 $0$、$1$ 或者 $2$，以及一个长度为 $N$ 的字符串 $S=S_1S_2\\dots S_N$，其中每个字符都是 M、E 或者 X。

找出满足条件 $S_iS_jS_k=$ MEX 的所有整数元组 $(i,j,k)$ 的 $\\text{mex}(A_i,A_j,A_k)$ 的和。这里，$\\text{mex}(A_i,A_j,A_k)$ 表示不等于 $A_i,A_j,A_k$ 的最小非负整数。

约束条件

• $3 \\leq N \\leq 2\\times 10^5$
• $N$ 是一个整数。
• $A_i \\in \\lbrace 0,1,2\\rbrace$
• $S$ 是一个长度为 $N$ 的字符串，由 M、E 和 X 组成。

输入

输入数据从标准输入中获取，格式如下：

$N$ $A_1$ $A_2$ $\\dots$ $A_N$ $S$

输出

将答案输出为一个整数。

示例输入 1

4
1 1 0 2
MEEX

示例输出 1

3

满足条件 $S_iS_jS_k=$ MEX 的整数元组 $(i,j,k)\\ (1 \\leq i < j < k \\leq N)$ 有两个：$(i,j,k)=(1,2,4),(1,3,4)$。因为 $\\text{mex}(A_1,A_2,A_4)=\\text{mex}(1,1,2)=0$，$\\text{mex}(A_1,A_3,A_4)=\\text{mex}(1,0,2)=3$，所以答案为 $0+3=3$。

示例输入 2

3
0 0 0
XXX

示例输出 2

0

示例输入 3

15
1 1 2 0 0 2 0 2 0 0 0 0 0 2 2
EXMMXXXEMEXEXMM

示例输出 3

13