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 1000$
$2$	$30$	$n\le 300000$, the tree is a chain — each node $x=1,\dots ,n-1$ is connected to node $x+1$.
$3$	$60$	$n\le 300000$

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