$N$ 個の頂点からなる木が与えられる。木の各頂点には $1$ から $N$ までの番号が付けられており、アルファベット U, C, P のうちの $1$ つが書かれている。このとき、次の条件を満たす順序対 $(a, b)$ の個数を求めよ。 ($1 \le a < b \le N$)

• 頂点 $a$ から頂点 $b$ に至る単純パスに含まれるすべての頂点に書かれた文字を集めて並べ替えることで、$(\text{UCPC})^k$ の形の文字列を作ることができる。 ($k \ge 1$)

入力

1行目に頂点の数 $N$ が与えられる。 ($1 \le N \le 200\,000$)

2行目にアルファベット U, C, P のみからなる長さ $N$ の文字列 $S$ が与えられる。 $S$ の $i$ 番目の文字は頂点 $i$ に書かれている文字を表す。

続く $N - 1$ 行にわたって、2つの整数 $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

注記

例1に対応する木は以下の通りである。

図 J.1: 例1に対応する木

1番の頂点と4番の頂点、1番の頂点と5番の頂点の間のパスを利用すると、$k = 1$ の形の文字列 ($\text{UCPC}$) を作ることができる。

例2の場合、$k = 1$ の形の文字列 ($\text{UCPC}$) 2個、$k = 2$ の形の文字列 ($\text{UCPCUCPC}$) 1個を作ることができる。