Petar is throwing a birthday party and he decided to invite some of the employees of his company where he is the CEO.

Each employee, including Petar, has a unique label from $1$ to $N$, and an accompanying type of jokes they tell $V_i$. Also, each employee of the company except Petar has exactly one supervisor.

Since Petar is the CEO of the company, he has the label $1$ and is directly or indirectly superordinate to all the employees.

At the birthday party, there are certain rules that all people present (including Petar) must follow.

• At the party, there shouldn't be two people that tell the same type of jokes.
• Person $X$ cannot be invited if their direct supervisor is not invited.
• Person $X$ cannot be invited if the set of jokes the invitees that person $X$ is superior to (directly or indirectly) tell and person $X$ don't form a set of consecutive numbers. The numbers in the set are consecutive if the difference between adjacent elements is exactly 1 when the set is sorted ascendingly. For example, $(3,1,2)$ and $(5,1,2,4,3)$.

Petar wants to know how many different sets of jokes he can see at his party with the listed constraints.

Input Specification

The first line of input contains the integer $N$ $(1\le N\le 10000)$.

The second line of input contains $N$ integers, the types of jokes person $i$ tells, $V_i$ $(1\le V_i\le 100)$.

Each of the following $N-1$ lines contains two integers $A$ and $B$ $(1\le A,B\le N)$, denoting that person $A$ is directly superior to person $B$.

In test cases worth 50% of total points, it will hold that $N$ does not exceed $100$.

Output Specification

The first and only line of output must contain the number of different sets of jokes that comply to the previously listed constraints.

Sample Input 1

4
2 1 3 4
1 2
1 3
3 4

Sample Output 1

6

Explanation of Sample Output 1

It is possible to have the following sets of jokes at the party:

$\{2\}$, $\{2,3\}$, $\{2,3,4\}$, $\{1,2,3,4\}$, $\{1,2\}$, $\{1,2,3\}$.

Sample Input 2

4
3 4 5 6
1 2
1 3
2 4

Sample Output 2

3

Explanation for Sample Output 2

The only possible sets of jokes are: $\{3\}$, $\{3,4\}$, $\{3,4,5\}$. Notice that the person telling joke $6$ cannot be at the party because, in that case, the set of jokes $\{4,6\}$ is not a set of consecutive numbers.

Sample Input 3

6
5 3 6 4 2 1
1 2
1 3
1 4
2 5
5 6

Sample Output 3

10