Усе добре

Обмеження: 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