A tree with $N$ vertices is given. Each vertex of the tree is numbered from $1$ to $N$, and has one of the letters U, C, P written on it. Find the number of ordered pairs $(a, b)$ satisfying the following condition ($1 \le a < b \le N$):

• By collecting all the characters written on the vertices included in the simple path from vertex $a$ to vertex $b$ and rearranging them, we can form a string of the form $(\text{UCPC})^k$ ($k \ge 1$).

Input

The first line contains the number of vertices $N$ ($1 \le N \le 200\,000$).

The next line contains a string $S$ of length $N$ consisting only of the alphabets U, C, P.

The next $N - 1$ lines each contain two integers $u_i$ and $v_i$ separated by a space. This means that vertex $u_i$ and vertex $v_i$ are directly connected in the tree. ($1 \le u_i, v_i \le N, u_i \ne v_i$)

Output

Print the number of pairs $(a, b)$ satisfying the condition.

Examples

Input 1

5
UCCPP
2 3
4 3
3 5
2 1

Output 1

2

Input 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

Output 2

3

Note

The tree corresponding to Example 1 is as follows.

Figure J.1: Tree corresponding to Example 1

Using the path between vertex 1 and vertex 4, and the path between vertex 1 and vertex 5, we can form a string of the form $\text{UCPC}$ ($k = 1$).

In the case of Example 2, we can form 2 strings of the form $\text{UCPC}$ ($k = 1$) and 1 string of the form $\text{UCPCUCPC}$ ($k = 2$).