Sabiha and the War Victims

Sabiha is working as a leader of the volunteers to help the victims of the Syrian Civil War. There are n cities where city 1 is the capital( i.e. root) and n-1 total roads in Syria. There is exactly one road connecting the two different cities of Syria. Sabiha has kept one volunteer at each city. Each volunteer has been given a Volunteer T-Shirt. T-shirt of the volunteer located at city i contains a number written on it, which is denoted by the integer c[i].

Since Sabiha is a great programmer. Seeing the road map of the cities and Sabiha’s plan, Sabiha’s mother Mou asked her a question: For each city, in how many ways can you list the Volunteer T-Shirt in the subtree of that city such that they form a palindromic sequence.
A palindromic sequence is such a sequence that the numbers in the sequence are read same from forward to backward and from backward to forward.
Since Sabiha is busy with her Volunteer work for the victims of the war, she asked you to solve the problem.

Input

The first line of the input contains an integer n denoting the number of cities in Syria.
The next line contains n integers c[i], where c[i] denotes the Volunteer T-Shirt number of the volunteer assigned at city i.

Each of the next n-1 lines contains two integers u and v, denoting there is a road between city u and v.

Constraints

1 ≤ n ≤ 200000
1 ≤ u, v ≤ n
1 ≤ c[i] ≤ 1000000000
City 1 is always the capital (root)

Output

Print n space separated integers, where the i-th integer denotes the number of ways to list the T-Shirt numbers in the subtree of city i such that it forms a palindromic sequence.
Since the answers can be a large number, print the answers modulo 1000000007.

Samples

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

2 1 1 1 1

4
100 80 80 50
1 2
1 3
2 4

0 0 1 1