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

• “()” 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 each 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 the node $a$ (at the first position) and the character written in the 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.

입력 형식

The first line of contains the an 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$^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 ≤ x, y ≤ n$) — the labels of nodes directly connected with an edge.

출력 형식

Output the required number of pairs.

예제 입력 1

4
(())
1 2
2 3
3 4

예제 출력 1

2

예제 입력 2

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

예제 출력 2

3

예제 입력 3

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

예제 출력 3

6