给定一个含有 $N$ 个结点的树。树的每个结点上都标有从 $1$ 到 $N$ 的编号，并且写有字符 U、C、P 中的一个。

请计算满足以下条件的有序对 $(a, b)$ 的数量（$1 \le a < b \le N$）：

• 收集从结点 $a$ 到结点 $b$ 的简单路径上包含的所有结点上的字符，并重新排列后，可以组成形如 $\text{(UCPC)}^k$ 的字符串（$k \ge 1$）。

输入格式

第一行给定结点的数量 $N$（$1 \le N \le 200\,000$）。

第二行给定一个长度为 $N$ 且仅由字符 U、C、P 组成的字符串 $S$。第 $i$ 个字符表示结点 $i$ 上的字符。

接下来的 $N - 1$ 行，每行给定两个用空格分隔的整数 $u_i$ 和 $v_i$，表示树中结点 $u_i$ 和结点 $v_i$ 之间有一条边直接相连（$1 \le u_i, v_i \le N, u_i \neq v_i$）。

输出格式

输出满足条件的有序对 $(a, b)$ 的数量。

样例

输入样例 1

5
UCCPP
2 3
4 3
3 5
2 1

输出样例 1

2

输入样例 2

13
CUUUCCCCPCCPP
1 2
2 3
4 7
3 10
6 2
7 6
12 13
9 7
7 8
11 12
7 11
5 7

输出样例 2

3

说明

对应样例 1 的树如下图所示。

图 J.1: 对应样例 1 的树

利用 1 号结点和 4 号结点、1 号结点和 5 号结点之间的路径，可以组成 $k = 1$ 形式的字符串 $\text{(UCPC)}$。

对于样例 2，可以组成 2 个 $k = 1$ 形式的字符串 $\text{(UCPC)}$，以及 1 个 $k = 2$ 形式的字符串 $\text{(UCPCUCPC)}$。