CF2194F1.Again Trees... (Easy Version)

This is the easy version of the problem. The difference between the versions is that in this version, $k \leq 4$. You can hack only if you solved all versions of this problem.

Given a tree consisting of $n$ vertices. Each vertex has a non-negative integer $a_v$ written on it. You are also given $k$ distinct non-negative integers $b_1, \ldots, b_k$.

We will call a set of edges beautiful if, after removing these edges from the tree, the tree splits into connected components, where in each component the bitwise XOR of all the numbers $a_v$ in that component belongs to the set $b$.

You need to count the number of beautiful sets of edges in the tree modulo $10^9 + 7$.

这是该问题的简单版本。两个版本的区别在于，在此版本中，$k \leq 4$。仅当您解决了该问题的所有版本时，才可进行 Hack。

给定一棵包含 $n$ 个顶点的树。每个顶点上写有一个非负整数 $a_v$。同时给定 $k$ 个互不相同的非负整数 $b_1, \ldots, b_k$。

我们称一组边为“优美的”，如果从树中移除这些边后，树被分割为若干连通分量，且每个连通分量内所有顶点上的数 $a_v$ 的按位异或（XOR）结果均属于集合 $b$。

您需要计算树中优美边集的数量，结果对 $10^9 + 7$ 取模。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 500$). The description of the test cases follows.

The first line of each dataset contains two integers $n$ and $k$ ($2 \leq n \leq 10^5$, $1 \leq k \leq 4$) — the number of vertices in the tree and the size of the set $b$.

The next $n - 1$ lines describe the edges of the tree. The $i$-th line contains two integers $v_i$ and $u_i$ ($1 \leq v_i, u_i \leq n$) — the numbers of the vertices connected by the $i$-th edge.

The next line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \leq a_i \lt 2^{30}$) — the values written on the vertices.

The following line contains $k$ distinct integers $b_1, b_2, \ldots, b_k$ ($0 \leq b_i \lt 2^{30}$) — the elements of the set $b$.

It is guaranteed that the sum of $n$ across all datasets does not exceed $10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $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$。

For each test dataset, output a single integer — the answer to the problem.

对于每个测试数据集，输出一个整数——即该问题的答案。

Illustration for the first test dataset. In it, you can remove the edge between vertices $1$ and $2$. Then the bitwise XOR in the component consisting of vertices $2$ and $5$ is $a_2 \oplus a_5 = 2 \oplus 3 = 1$. The bitwise XOR in the component with vertices $1$, $3$, and $4$ is $a_1 \oplus a_3 \oplus a_4 = 0 \oplus 2 \oplus 3 = 1$. The second beautiful set is the one consisting of the edge connecting vertices $1$ and $3$.

In the third test dataset, the beautiful sets will be (an edge is denoted by the pair of vertices it connects) $[(1, 2)], [(1, 3)], [(2, 5)], [(3, 4)]$. Note that the first and third samples differ only in the set $b$.

In the fourth test dataset, the beautiful sets will be $[(1, 2)], [(3, 4)], [(1, 2), (2, 3), (3, 4)]$.

第一个测试数据集的示意图。在此图中，你可以删除顶点 $1$ 和 $2$ 之间的边。此时，由顶点 $2$ 和 $5$ 构成的连通分量的按位异或值为 $a_2 \oplus a_5 = 2 \oplus 3 = 1$；由顶点 $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)]$。