这是问题的困难版本。版本之间的差异在于,在此版本中,$$$k \leq 10$$$。只有解决了该问题的所有版本,您才能破解。
给定一棵由 $$$n$$$ 顶点组成的树。每个顶点上都写有一个非负整数$$$a_v$$$。您还会获得 $$$k$$$ 不同的非负整数 $$$b_1, \ldots, b_k$$$。
如果从树中删除这些边后,树分裂成连接的组件,其中每个组件中的按位 该分量中所有数字 $$$a_v$$$ 的 异或 属于集合 $$$b$$$。
您需要计算树中美丽边集的数量,以 $$$10^9 + 7$$$ 为模。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 500$$$)。测试用例的描述如下。
每个数据集的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$2 \leq n \leq 10^5$$$, $$$1 \leq k \leq 10$$$) - 树中的顶点数和集合 $$$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$$$。
输出
对于每个测试数据集,输出一个整数 - 问题的答案。
示例
输入复制
45 11 21 33 42 50 2 2 3 315 14 51 23 13 50 0 2 0 205 21 21 33 42 50 2 2 3 31 34 11 22 33 41 1 1 11
输出复制
2843
注意
第一个测试数据集的插图。在其中,您可以删除顶点 $$$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)]$$$。