A shopping mall has $n$ kiosks numbered from 1 to $n$, with the $i$-th kiosk selling item $c_i$. The mall has $n-1$ bidirectional roads numbered from 1 to $n-1$, with the $i$-th road connecting kiosk $u_i$ and kiosk $v_i$. The road system ensures connectivity between any two kiosks. During the pandemic, it is desired to shut down some kiosks to easily control shopping activities and customer interactions. When a kiosk is shut down, all roads connected to that kiosk are blocked for security reasons. Additionally, to minimize the impact on customers, the mall wants to ensure that the remaining operational kiosks satisfy the following two conditions:
- The remaining operational kiosks must be connected: That is, there must be a path (through unblocked roads) between any two operational kiosks.
- All essential items numbered from 1 to $k$ must be sold at least at one operational kiosk.
Two plans are considered different if there is a kiosk that is shut down in one plan but opened in the other.
Requirement: Determine the number of different plans that satisfy the above conditions.
### Input
- Line 1 contains a positive integer $n \le 10^4, k \le 10$
- Line 2 contains $n$ positive integers $c_1,c_2,...,c_n$ with $c_i \le n$ for all positive integers $i \le n$
- The next $n-1$ lines, the $i$-th line contains two positive integers $u_i,v_i$
The numbers on the same line of input are separated by spaces.
### Output
- Print a single integer which is the remainder when the number of plans satisfying the conditions is divided by $1000000007$ $(10^9 + 7)$
### Constraints
- Subtask 1 (30% of the points): $k = 1$
- Subtask 2 (30% of the points): Each kiosk has no more than $2$ roads connected to it.
- Subtask 3 (40% of the points): No additional constraints beyond those stated in the problem.
### Example
Input:
```
4 3
1 2 4 3
1 2
2 3
3 4
```
Output:
```
1
```
Input:
```
5 2
1 2 2 2 3
1 2
1 3
1 4
2 5
```
Output:
```
11
```
