All is well

Limits: 4 sec., 256 MiB

This statement was translated automatically from Ukrainian.

The Burdock virus continues to rage through the city of Morshyn, infecting district after district.

For simplicity, let’s imagine that the city consists of districts, some of which are connected by bidirectional roads. In total, the city has \(n\) districts and \(n-1\) roads. Also, for any two districts, there exists a sequence of roads connecting these two districts.

Fortunately, the Morshyn City Council knows exactly how to properly combat the virus. At an extraordinary meeting of the council, it was decided to completely block \(k - 1\) roads, thereby forming \(k\) quarantine zones. A quarantine zone — is such a maximal by inclusion set of districts of the city, between each pair of which there will exist a path along unblocked roads.

After consultation with local immunologists, the deputies concluded that for maximum efficiency, the sizes of the quarantine zones must be \(a_1\), \(a_2\), ..., \(a_k\). In such a case, the residents of Morshyn are not threatened by the virus.

Your task — is to find the number of ways to block \(k - 1\) roads to achieve the desired sizes of the quarantine regions. Two ways are different if different sets of roads are blocked. Since the answer can be very large, output the remainder of the division of the answer by the prime number \(10^9 + 7\).

Input

The first line is given two positive integers \(n\) and \(k\) — the number of districts in Morshyn and the number of quarantine zones that need to be formed.

The second line is given \(k\) positive integers \(a_i\) — the sizes of the quarantine zones.

In the next \(n-1\) lines are given pairs of numbers \(u_i\), \(v_i\) — the numbers of districts connected by the corresponding road.

Output

In a single line, output one integer — the remainder of the division of the answer by \(10^9 + 7\).

Constraints

\(2 \le n \le 10^5\),

\(2 \le k \le 7\),

\(1 \le a_i \le n\),

\(\sum a_i = n\),

\(1 \le u_i, v_i \le n\).

Samples

Input (stdin) сopy	Output (stdout) сopy
6 2 5 1 1 2 1 3 1 4 4 5 4 6	4