Big task#11095
This time, Doofenshmirtz conceived such a big dirty trick that Perry can't handle it alone. Therefore, he decided to call his special agents from O.B.K.A.
In the office of O.B.K.A. there are offices that are connected with n - 1 corridors. From any office you can get through the corridors to any other. In other words, the office of O.B.K.A. is a tree, the vertices of which correspond to the offices, and the edges to the corridors. There is exactly one special agent in each office, in office number there is a special agent with the skill c_v. There are different skills in total, numbered from to .
Perry wants to select a special agent squad such that for each of the skills in this squad there will be at least one special agent with that skill. Also, if Perry takes the special agents from offices and into the squad, he will also definitely take into the squad all the special agents who sit in the offices located on the path between and .
Help Perry figure out the number of ways he can choose a squad for a mission. Since this number can be large, print the remainder after dividing this number by .
The first line contains two integers and (1 \le n \le 10^4, 1 \le m \le 10) - the number of offices and the number of different skills.
The next line contains integers c_i (1 \le c_i \le m) - the skills of the special agents.
The next n - 1 lines contain two integers a_i and b_i (1 \le a_i, b_i \le n) - numbers of offices connected by -th corridor.
It is guaranteed that the office of O.B.K.A. represents a tree.
Print a single integer - the number of ways to choose a squad of special agents modulo .
Example 1
Example 2
Example 3