During the season of autumn, leaves change colours and fall to the ground. To celebrate the autumn spirit, you are given a tree with ~N~ nodes and ~K~ different colours, where each node has a colour ~a_i~, and ~1 \le a_i \le K~. For each colour ~C~ from ~1~ to ~K~, you must answer a query on the tree. The following process occurs: every second, a random leaf node is removed from the tree, falling to the ground. This process ends when colour ~C~ is completely removed from the tree, or there is only ~1~ node left. Out of every possible sequence of falling leaves, determine the number of sequences where colour ~C~ is completely removed from the tree in the shortest amount of time. Note that if the colour does not exist, or the colour cannot be removed, there are ~0~ sequences where it is removed.

Constraints

~1 \le K \le N \le 3 \times 10^5~

~1 \le a_i \le K~

~1 \le u_i,v_i \le N~

Subtask 1 [30%]

~1 \le N \le 3 \times 10^3~

Subtask 2 [70%]

No additional constraints.

Input Specification

The first line contains ~2~ space-separated integers ~N~ and ~K~.

The next line contains ~N~ space-separated integers, the ~i~-th of which is ~a_i~.

The next ~N-1~ lines contain ~2~ space-separated integers ~u_i~ and ~v_i~, denoting an edge between nodes ~u_i~ and ~v_i~.

Output Specification

Output ~K~ lines, where the ~C~-th line contains the number of sequences where colour ~C~ is completely removed from the tree in the shortest amount of time. Since these numbers may be large, please output the answers modulo ~10^9+7~.

Sample Input

10 3
1 3 3 2 1 3 1 1 2 2
1 6
3 9
4 6
5 2
2 10
7 10
8 6
6 9
9 10

Sample Output

24
105
630