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 n 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 v there is a special agent with the skill cv. There are m different skills in total, numbered from 1 to m.

Perry wants to select a special agent squad such that for each of the m skills in this squad there will be at least one special agent with that skill. Also, if Perry takes the special agents from offices v and u 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 u and v.

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 998 244 353.

Input

The first line contains two integers n and m (1 ≤ n ≤ 104, 1 ≤ m ≤ 10) - the number of rooms and the number of different skills.

The next line contains n integers ci (1 ≤ ci ≤ m) - the skills of the special agents.

The next n - 1 lines contain two integers ai and bi (1 ≤ ai, bi ≤ n) - numbers of rooms connected by i-th corridor.

It is guaranteed that the office of O.B.K.A. represents a tree.

Output

Print a single integer - the number of ways to choose a squad of special agents modulo 998 244 353.