給定一棵擁有 $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$。

接下來的 $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$ 形式的字串（UCPC）。

對於範例 2，可以組成 2 個 $k = 1$ 形式的字串（UCPC），以及 1 個 $k = 2$ 形式的字串（UCPCUCPC）。