You are given an undirected tree with n nodes. The nodes are numbered 1 through n. Each node is labeled with either ‘(’ or ‘)’. Let l[u → v] denote the string obtained by concatenating the labels of the nodes on the simple path from u to v. (Note that the simple path between two nodes is uniquely determined on a tree.) A balanced string is defined as follows:</p>

• The empty string is balanced.
• For any balanced string s, the string “(”s“)” is balanced.
• For any balanced strings s and t, the string st (the concatenation of s and t) is balanced.
• Any other string is NOT balanced.

Calculate the number of the ordered pairs of the nodes (u, v) such that l[u → v] is balanced.

입력 형식

The input consists of a single test case. The input starts with an integer n (2 ≤ n ≤ 10⁵), which is the number of nodes of the tree. The next line contains a string of length n, each character of which is either ‘(’ or ‘)’. The x-th character of the string represents the label of the node x of the tree. Each of the following n − 1 lines contains two integers ai and bi (1 ≤ ai , bi ≤ n), which represents that the node ai and the node bi are connected by an edge. The given graph is guaranteed to be a tree.

출력 형식

Display a line containing the number of the ordered pairs (u, v) such that l[u → v] is balanced.

예제 입력 1

2
()
1 2

예제 출력 1

1

예제 입력 2

4
(())
1 2
2 3
3 4

예제 출력 2

2

예제 입력 3

5
()())
1 2
2 3
2 4
1 5

예제 출력 3

4