Усе добре
Обмеження: 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 |
Надіслати розв'язок
Element Type | Створено | Хто | Задача | Компілятор | Результат | Час (сек.) | Пам'ять (МіБ) | № | Дії |
---|
Element Type | Створено | Хто | Задача | Компілятор | Результат | Час (сек.) | Пам'ять (МіБ) | № | Дії |
---|