Підрахунок на дереві#431
Вам задано дерево з вершинами. Кожній вершині відповідає число a_i (0 \leq a_i \leq 1).
Множина вершин називається прекрасною, якщо виконуються такі умови:
не порожня.
є зв'язною. Тобто, якщо вершини і належать , то всі вершини на простому шляху між і також належать .
Сума усіх a_u для u \in S дорівнює , де — задане число.
Потрібно підрахувати кількість прекрасних множин. Оскільки ця кількість може бути дуже великою, виведіть відповідь за модулем 10^9 + 7.
Перший рядок містить кількість тестів . Кожен тест складається з наступних рядків:
Перший рядок містить два цілих числа (1 \leq n \leq 50000) і (1 \leq k \leq 100).
Другий рядок містить цілих чисел a_1, a_2, \ldots, a_n.
Кожен з наступних n-1 рядків містить два цілих числа і (1 \leq u, v \leq n), що означає наявність ребра між та . Гарантовано, що ці ребра утворюють дерево.
Для кожного тесту виведіть відповідь в окремому рядку.
Приклад 1