Дано дерево с $N$ вершинами. Вершины дерева пронумерованы от 1 до $N$, и на каждой из них записан один из символов U, C или P. Найдите количество пар $(a, b)$, удовлетворяющих следующим условиям ($1 \le a < b \le N$):

• Если собрать все символы, записанные на вершинах простого пути между вершиной $a$ и вершиной $b$, то их можно переставить таким образом, чтобы получить строку вида $(UCPC)^k$ ($k \ge 1$).

Входные данные

В первой строке задано количество вершин $N$ ($1 \le N \le 200\,000$).

Во второй строке задана строка $S$ длины $N$, состоящая только из символов U, C и P. $i$-й символ строки $S$ соответствует символу, записанному на вершине $i$.

В следующих $N - 1$ строках заданы по два целых числа $u_i$ и $v_i$, разделенных пробелом. Это означает, что в дереве есть ребро между вершинами $u_i$ и $v_i$ ($1 \le u_i, v_i \le N$, $u_i \ne 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

Примечание

Дерево, соответствующее первому примеру, изображено ниже:

Рисунок J.1: Дерево для примера 1

Используя путь между вершинами 1 и 4, а также путь между вершинами 1 и 5, можно получить строку вида $(UCPC)^k$ при $k = 1$.

В случае примера 2 можно получить 2 строки вида $(UCPC)^k$ при $k = 1$ и 1 строку вида $(UCPC)^k$ при $k = 2$.