Se da un árbol con $N$ vértices. Cada vértice del árbol está numerado del $1$ al $N$, y tiene escrita una de las letras del alfabeto: U, C o P.

Encuentra el número de pares ordenados $(a, b)$ que satisfacen la siguiente condición ($1 \le a < b \le N$):

• Al reunir todas las letras escritas en los vértices incluidos en el camino simple desde el vértice $a$ hasta el vértice $b$ y reordenarlas, se puede formar una cadena de la forma $(\text{UCPC})^k$ ($k \ge 1$).

Entrada

La primera línea contiene el número de vértices $N$ ($1 \le N \le 200\,000$).

La siguiente línea contiene una cadena $S$ de longitud $N$ que consiste únicamente de las letras U, C y P. La $i$-ésima letra de $S$ representa la letra escrita en el vértice $i$.

Las siguientes $N - 1$ líneas contienen dos enteros $u_i$ y $v_i$ separados por un espacio. Esto significa que el vértice $u_i$ y el vértice $v_i$ están conectados directamente por una arista en el árbol. ($1 \le u_i, v_i \le N$, $u_i \neq v_i$)

Salida

Imprime el número de pares $(a, b)$ que satisfacen la condición.

Ejemplos

Entrada 1

5
UCCPP
2 3
4 3
3 5
2 1

Salida 1

2

Entrada 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

Salida 2

3

Nota

El árbol correspondiente al Ejemplo 1 es el siguiente:

Figura J.1: Árbol correspondiente al Ejemplo 1

Si se utiliza el camino entre el vértice 1 y el vértice 4, o entre el vértice 1 y el vértice 5, se puede formar una cadena de la forma $(\text{UCPC})^k$ con $k = 1$.

En el caso del Ejemplo 2, se pueden formar 2 cadenas de la forma $(\text{UCPC})^k$ con $k = 1$, y 1 cadena de la forma $(\text{UCPC})^k$ con $k = 2$.