Усе добре

Обмеження: 4 сек., 256 МіБ

Реп’яховiрус продовжує вирувати мiстом Моршин, заражаючи квартал за кварталом.

Для простоти уявимо, що місто складається з кварталів, деякі з яких з’єднані двосторонніми дорогами. Усього в місті є \(n\) кварталів та \(n-1\) дорога. Також, для будь-яких двох кварталів існує послідовність доріг, які з’єднують ці два квартали.

На щастя, Моршинська міська рада точно знає як правильно боротися з вірусом. На позачерговому засіданні ради було прийнято рішення повністю перекрити \(k - 1\) дорогу, таким чином утворивши \(k\) карантинних районів. Карантинний район — така максимальна по включенню множина кварталів міста, між кожною парою яких буде існувати шлях по неперекритих дорогах.

Після консультації з місцевими імунологами, депутати дійшли висновку, що для максимальної ефективності, розміри карантинних районів повинні бути \(a_1\), \(a_2\), ..., \(a_k\). У такому випадку жителям Моршина вірус не загрожує.

Ваше завдання — знайти кількість способів перекрити \(k - 1\) дорогу, щоб досягнути бажаних розмірів карантинних регіонів. Два способи є різними, якщо перекриваються різні набори доріг. Оскільки відповідь може бути дуже великою, виведіть остачу від ділення відповіді на просте число \(10^9 + 7\).

Вхідні дані

У першому рядку задано два натуральні числа \(n\) та \(k\) — кількість кварталів в Моршині та кількість карантинних районів, які необхідно утворити.

У другому рядку задано \(k\) натуральних чисел \(a_i\) — розміри карантинних районів.

У наступних \(n-1\) рядках задано пари чисел \(u_i\), \(v_i\) — номери кварталів які з’єднує відповідна дорога.

Вихідні дані

У єдиному рядку виведіть одне ціле число — остачу від ділення відповіді на \(10^9 + 7\).

Обмеження

\(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\).

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
6 2 5 1 1 2 1 3 1 4 4 5 4 6	4