技能树

时间限制：3.5 秒
内存限制：512 MB
输入：标准输入
输出：标准输出

在任何策略游戏中，包括《文明》，都有许多技能可供玩家学习和获得。

《文明》中的 $n$ 个技能每个都有一个类型——军事、文化、建造等。我们用整数 $c_i$ 表示第 $i$ 个技能的类型。技能按一棵有根树组织——每个技能都有一个前置技能，必须先学习它才能解锁该技能。学习过程从树根开始——即基础技能，直接或间接地需要它来解锁所有其他技能。

我们说两个技能 $u$ 和 $v$ 相似，如果它们子树中的技能类型多重集相同。换言之，要使两个技能相似，它们的子树中每种类型的技能数量必须相等。

《文明 VII》尚未发布，开发人员正在测试关于技能树应如何构建的各种假设。为此，他们会进行 $q$ 次操作，每次将树重新根到另一个顶点，并计算相似技能的对数。当树重新根到技能 $v$ 时，$v$ 成为根（第一个要学习的技能），树的所有其他边保持不变，但某些边上的父子关系会相应改变。

对于每次重根查询，请计算执行查询后相似技能的无序对数量。“无序对”意味着 $(u, v)$ 和 $(v, u)$ 算作同一对。由于答案可能很大，请输出其对 $10^9 + 7$ 取模的结果。

输入格式

每个测试包含多组测试数据。第一行包含一个整数 $t$ —— 测试数据的组数 ($1 \le t \le 2 \cdot 10^5$)。接下来是每组测试数据的描述。

每组测试数据的第一行包含一个整数 $n$ —— 游戏中的技能数量 ($2 \le n \le 2 \cdot 10^5$)。

第二行包含 $n$ 个整数 $c_i$ —— 技能的类型 ($1 \le c_i \le 10^9$)。

接下来的 $n-1$ 行中，第 $i$ 行包含两个整数 $u_i$ 和 $v_i$ —— 两个直接依赖的技能编号 ($1 \le u_i, v_i \le n$)。哪个技能依赖哪个由哪个技能被选为“根”决定。保证依赖结构构成一棵树。

下一行包含一个整数 $q$ —— 对技能树进行重根操作的查询次数 ($1 \le q \le n$)。

最后一行包含 $q$ 个整数 $x_i$ —— 作为新根的顶点编号 ($1 \le x_i \le n$)。

保证所有测试数据中 $n$ 的总和不超过 $2 \cdot 10^5$。

输出格式

对于每个查询，输出一行，表示相似技能对的数量对 $10^9 + 7$ 取模的结果。

评分系统

仅当该子任务及其所需子任务的所有测试均通过时，才获得对应分数。

样例

样例 1

输入

1
7
1 1 2 4 3 3 4
1 2
1 3
2 4
4 5
3 6
3 7
7
1 2 3 4 5 6 7

输出

1
1
1
1
0
0
1

样例 2

输入

1
7
1 2 2 3 3 3 3
1 2
1 3
2 4
4 5
3 6
3 7
7
1 2 3 4 5 6 7

输出

4
3
3
3
1
1
1

```