eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Подсчет на дереве

Подсчет на дереве

Лимит времени 1 секунда
Лимит использования памяти 122 MiB

Задано дерево из n вершин, с каждой вершиной i связано число a[i] (0a[i]1).

Назовем множество S вершин дерева прекрасным, если имеют место следующие условия:

  • S не пустое.

  • S связное. То есть если вершины u и v принадлежат S, то все вершины на простом пути между u и v также принадлежат S.

  • Сумма всех a[u] (u принадлежит S) равна k, где k - заданное число.

Вам следует подсчитать количество прекрасных множеств. Поскольку их число может быть большим, то ответ следует вывести по модулю 10^9 + 7.

Входные данные

Первая строка содержит количество тестов t. Каждый тест состоит из следующих строк:

  • первая строка содержит два целых числа n (1n50000) и k (1k100).

  • Вторая строка содержит n целых чисел a[1], a[2], ..., a[n].

  • Каждая из следующих n - 1 строк содержит пары чисел u и v (1u, vn) указывающих на наличие ребра между вершинами u и v. Гарантируется, что заданные ребра образуют дерево.

Выходные данные

Для каждого теста вывести ответ в отдельной строке.

Пример

Входные данные #1
3
3 1
1 0 1 
1 2
1 3
5 2
0 1 0 1 1 
1 2
1 3
1 4
2 5
3 0
1 1 0 
1 2
2 3
Выходные данные #1
3
5
1