An expression is a string consisting only of properly paired brackets. For example, ()() and (()()) are expressions, whereas )( and ()( are not. We can define expressions inductively as follows:

• () is an expression.
• If ~a~ is an expression, then ~(a)~ is also an expression.
• If ~a~ and ~b~ are expressions, then ~ab~ is also an expression.

A tree is a structure consisting of ~n~ nodes denoted with numbers from ~1~ to ~n~ and ~n-1~ edges placed so there is a unique path between every two nodes. Additionally, a single character is written in each node. The character is either an open bracket ( or a closed bracket ). For different nodes ~a~ and ~b~, ~w_{a,b}~ is a string obtained by traversing the unique path from ~a~ to ~b~ and, one by one, adding the character written in the node we're passing through. The string ~w_{a,b}~ also contains the character written in node ~a~ (at the first position) and the character written in node ~b~ (at the last position).

Find the total number of pairs of different nodes ~a~ and ~b~ such that ~w_{a,b}~ is a correct expression.

Input Specification

The first line contains the integer ~n~ — the number of nodes in the tree. The following line contains an ~n~-character string where each character is either ) or (, the ~j^\text{th}~ character in the string is the character written in the node ~j~. Each of the following ~n-1~ lines contains two different positive integers ~x~ and ~y~ ~(1 \le x, y \le n)~ — the labels of nodes directly connected with an edge.

Output Specification

Output the required number of pairs.

Constraints

Subtask	Score	Constraints
~1~	~10~	~n \le 1\,000~
~2~	~30~	~n \le 300\,000~, the tree is a chain — each node ~x = 1, \dots, n-1~ is connected to node ~x+1~.
~3~	~60~	~n \le 300\,000~

Sample Input 1

4
(())
1 2
2 3
3 4

Sample Output 1

2

Sample Input 2

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

Sample Output 2

3

Sample Input 3

7
)()()((
1 2
1 3
1 6
2 4
4 5
5 7

Sample Output 3

6