Подсчет на дереве
Задано дерево из 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. Гарантируется, что заданные ребра образуют дерево.
Выходные данные
Для каждого теста вывести ответ в отдельной строке.