Підрахунок на дереві
У вас є дерево з n вершинами, де кожній вершині i відповідає число a[i] (0 ≤ a[i] ≤ 1).
Множина вершин S вважається прекрасною, якщо виконуються такі умови:
S не є порожньою.
S є зв'язною. Це означає, що якщо вершини u та v належать S, то всі вершини на простому шляху між u та v також повинні належати S.
Сума всіх
a[u]для вершин u, що належать S, дорівнює k, де k — задане число.
Вам потрібно підрахувати кількість таких прекрасних множин. Оскільки їх кількість може бути дуже великою, виведіть результат за модулем 10^9 + 7.
Вхідні дані
Перший рядок містить кількість тестів t. Кожен тест складається з наступних рядків:
Перший рядок містить два цілі числа n (1 ≤ n ≤ 50000) і k (1 ≤ k ≤ 100).
Другий рядок містить n цілих чисел
a[1],a[2], ...,a[n].Кожен з наступних n - 1 рядків містить пари чисел u і v (1 ≤ u, v ≤ n), які вказують на наявність ребра між вершинами u та v. Гарантується, що задані ребра утворюють дерево.
Вихідні дані
Для кожного тесту виведіть відповідь в окремому рядку.