F1. Опять деревья... (простая версия)
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Это простая версия задачи. Отличие между версиями заключается в том, что в этой версии $$$k \leq 4$$$. Вы можете делать взломы только в том случае, если решили все версии этой задачи.

Дано дерево, состоящее из $$$n$$$ вершин. На каждой вершине записано целое неотрицательное число $$$a_v$$$. Также вам дано $$$k$$$ различных целых неотрицательных чисел $$$b_1, \ldots, b_k$$$.

Будем называть множество рёбер красивым, если после удаления этих рёбер из дерева дерево распадается на компоненты связности, где в каждой из компонент побитовый XOR всех чисел $$$a_v$$$ в этой компоненте принадлежит множеству $$$b$$$.

Требуется посчитать количество красивых множеств рёбер в дереве по модулю $$$10^9 + 7$$$.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 500$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$k$$$ ($$$2 \leq n \leq 10^5$$$, $$$1 \leq k \leq 4$$$) — количество вершин в дереве и размер множества $$$b$$$.

Следующие $$$n - 1$$$ строк описывают рёбра дерева. $$$i$$$-я из них содержит два целых числа $$$v_i$$$ и $$$u_i$$$ ($$$1 \leq v_i, u_i \leq n$$$) — номера вершин, соединённых $$$i$$$-м рёбером.

Следующая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i \lt 2^{30}$$$) — значения, записанные на вершинах.

Следующая строка содержит $$$k$$$ целых различных чисел $$$b_1, b_2, \ldots, b_k$$$ ($$$0 \leq b_i \lt 2^{30}$$$) — элементы множества $$$b$$$.

Гарантируется, что сумма $$$n$$$ по всем наборам данных не превосходит $$$10^5$$$.

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

Для каждого набора входных данных выведите единственное целое число — ответ на задачу.

Пример
Входные данные
4
5 1
1 2
1 3
3 4
2 5
0 2 2 3 3
1
5 1
4 5
1 2
3 1
3 5
0 0 2 0 2
0
5 2
1 2
1 3
3 4
2 5
0 2 2 3 3
1 3
4 1
1 2
2 3
3 4
1 1 1 1
1
Выходные данные
2
8
4
3
Примечание

Иллюстрация к первому набору входных данных. В нём можно удалить ребро между вершинами $$$1$$$ и $$$2$$$. Тогда побитовый XOR в компоненте, состоящей из вершин $$$2$$$ и $$$5$$$, равен $$$a_2 \oplus a_5 = 2 \oplus 3 = 1$$$. Побитовый XOR в компоненте вершин $$$1$$$, $$$3$$$ и $$$4$$$ равен $$$a_1 \oplus a_3 \oplus a_4 = 0 \oplus 2 \oplus 3 = 1$$$. Вторым красивым набором является множество, состоящее из ребра, соединяющего вершины $$$1$$$ и $$$3$$$.

В третьем наборе входных данных красивыми будут множества (ребро обозначается парой вершин, которые оно соединяет) $$$[(1, 2)], [(1, 3)], [(2, 5)], [(3, 4)]$$$. Обратите внимание, что первый и третий примеры отличаются только множеством $$$b$$$.

В четвёртом наборе входных данных красивыми будут множества $$$[(1, 2)], [(3, 4)], [(1, 2), (2, 3), (3, 4)]$$$.