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

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

• S не пустое.
• S связное. То есть если вершины u и v принадлежат S, то все вершины на простом пути между u и v также принадлежат S.
• Сумма всех au (u принадлежит S) равна k, где k - заданное число.

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

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

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

• первая строка содержит два целых числа n (1 ≤ n ≤ 50000) и k (1 ≤ k ≤ 100).
• Вторая строка содержит n целых чисел a1, a2, ..., an.
• Каждая из следующих n - 1 строк содержит пары чисел u и v (1 ≤ u, v ≤ n) указывающих на наличие ребра между вершинами u и v. Гарантируется, что заданные ребра образуют дерево.

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

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