409474: GYM103575 E Draft Laws

Julia's dream has finally come true! She became the head of the Department of General Innopolis Management! In her department, everything is done in the most modern way: bureaucracy proceeds using the latest generation software.

There are $$$n$$$ employees in the department, each one of them has a dedicated computer. Let us number them with unique integer IDs from $$$1$$$ to $$$n$$$. Some pairs of computers are connected with a cable, which allows transferring data in both ways. Besides that, there is exactly one way to transfer data via cables between each two given computers, if we only allow using each cable at most once. In other words, the network of computers and cables forms a tree.

Currently, the department works on $$$k$$$ draft laws. Julia has to make a work schedule for tomorrow: for every employee, she has to decide which one out of $$$k$$$ draft laws they will work on. Every employee must work on exactly one draft law throughout the day. A draft law can be edited on several computers at once (or even on no computers). However, there is an exception: two computers connected with a cable must work on different draft laws to avoid concurrency issues. Also, some employees are assigned to a specific draft law, and they will only work on that law.

Julia is very excited for her first working day, and she is curious about the number of ways to create a work schedule for tomorrow. Help her find the desired number of ways! Since the answer may be too large, find the answer modulo $$$10^9+7$$$.

The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 3 \cdot 10^5$$$, $$$2 \le k \le 10^9$$$) — the number of computers in the department and the number of draft laws in development.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le k$$$), where $$$a_i$$$ is the number of a draft law of the $$$i$$$-th employee is assigned to, or $$$0$$$ if they are ready to work on anything.

The next $$$n - 1$$$ lines contain two integers $$$u_j$$$ and $$$v_j$$$ each — IDs of computers connected with a cable ($$$1 \le u_j, v_j \le n$$$; $$$u_j \neq v_j$$$). It is guaranteed that the network of computers and cables forms a tree.

Print a single integer — the number of ways to make a work schedule for tomorrow, modulo $$$10^9+7$$$.

4 3
0 0 1 2
1 2
2 3
2 4

2

4 3
1 0 0 0
1 2
2 3
2 4

8

4 1000000000
0 2 2 0
1 2
2 3
3 4

0

In the first example, computers $$$3$$$ and $$$4$$$ are already assigned with draft laws $$$1$$$ and $$$2$$$, so for computer $$$2$$$ there is only one possible draft law: $$$3$$$. And for computer $$$1$$$, we can choose two draft laws ($$$1$$$ and $$$2$$$), so the answer is $$$2$$$.

In the third example two connected computers $$$2$$$ and $$$3$$$ are already assigned with the same draft law $$$2$$$. Therefore, no plan can satisfy the requirements.