题目描述

伊尔达尔决定投身抽象艺术。他选择了一棵有 $n$ 个顶点的有根树作为画作的基础：这是一张无环图，其中顶点 $1$ 被指定为根。根没有父节点；对于任意其他顶点 $u \ge 2$，从 $u$ 到根的路径上的第一个顶点称为 $u$ 的父节点，记作 $p_u$。以 $v$ 为父节点的顶点称为 $v$ 的孩子。没有孩子的顶点称为叶子。保证根至少有两个孩子。

我们对树执行深度优先遍历：首先访问根，然后按顺序递归地以同样方式访问其孩子的子树。树的顶点按照该深度优先遍历的顺序编号。因此，对于每个 $i$ 从 $1$ 到 $n$，顶点 $i$ 的子树中的顶点编号构成一段连续的整数。

设树中有 $m$ 片叶子。伊尔达尔将它们按编号升序写出，得到序列 $l_1 < l_2 < \ldots < l_m$，并添加边连接所有形如 $(l_j, l_{j+1})$ 的叶子对，同时连接 $l_m$ 和 $l_1$。所添加的环 $l_1 \to l_2 \to \ldots \to l_m \to l_1$ 称为外环。

伊尔达尔将得到的图画在平面上，方式如下：外环被画作一个圆，叶子 $l_1, l_2, \ldots, l_m$ 沿圆周逆时针排列，圆周上相邻顶点间的弧表示外环的边。树的其他顶点表示为位于圆内的不同点。树的边用顶点间的线段表示，且顶点和边的位置使得边线段之间没有公共内点。下图展示了树的一种绘制方式。

:::align{center} :::

在伊尔达尔的图中，外环圆周内部的平面部分被图的边分割成了 $m$ 个区域，称为面。如果两个不同的面共享一条边，则称它们为相邻的面。例如，上图中得到 5 个面，分别记为 $\Gamma_1, \Gamma_2, \Gamma_3, \Gamma_4$ 和 $\Gamma_5$。

:::align{center} :::

上图中相邻的面对为 $(\Gamma_1, \Gamma_2)$、$(\Gamma_1, \Gamma_5)$、$(\Gamma_2, \Gamma_3)$、$(\Gamma_2, \Gamma_4)$、$(\Gamma_2, \Gamma_5)$、$(\Gamma_3, \Gamma_4)$ 和 $(\Gamma_4, \Gamma_5)$。

为了完成画作，伊尔达尔计划将每个面染成 $k$ 种颜色之一。一种染色被称为正确的，如果相邻的面被染成不同的颜色。伊尔达尔将图画中不同正确染色的个数对 $10^9+7$ 取模的结果称为该图画的潜能。

在评估了初始图画的潜能之后，伊尔达尔对该图的边进行了 $q$ 次操作。考虑第 $i$ 次操作，它由一个数 $v_i$ 给出，并对连接顶点 $v_i$ 和 $p_{v_i}$ 的树边生效。如果该边当前在图中可见，则伊尔达尔从图中删除该边；如果该边当前不在图中，则重新画上。每次修改后，图中的面的集合可能发生变化：删除边时，两个面可能合并成一个；画上边时，一个面可能分裂成两个。例如，若在上图中删除边 $8 - 9$，则面 $\Gamma_4$ 和 $\Gamma_5$ 合并成一个面 $\Gamma_{4+5}$。

:::align{center} :::

此时图中相邻的面对为 $(\Gamma_1, \Gamma_2)$、$(\Gamma_1, \Gamma_{4+5})$、$(\Gamma_2, \Gamma_3)$、$(\Gamma_2, \Gamma_{4+5})$ 和 $(\Gamma_3, \Gamma_{4+5})$。

每次操作后，需要重新确定该图画的潜能：即用不超过 $k$ 种颜色对面进行正确染色的方案数对 $10^9+7$ 取模的结果。

输入格式

第一行包含一个整数 $t$（$1 \le t \le 10\,000$），表示测试数据的组数。接下来是 $t$ 组数据的描述。

每组数据的第一行包含三个整数 $n$、$k$ 和 $q$（$3 \le n \le 10^6$，$2 \le k \le 10^9$，$0 \le q \le 300\,000$），分别表示树中的顶点数、可用颜色数和执行的操作次数。

每组数据的第二行包含 $p_2, p_3, \ldots, p_n$（$1 \le p_i < i$），其中 $p_i$ 是树中顶点 $i$ 的父节点。保证树的顶点按深度优先遍历顺序编号，且数值 $1$ 在 $p_2, \ldots, p_n$ 中出现至少两次。

随后是 $q$ 行，其中第 $i$ 行包含一个整数 $v_i$（$2 \le v_i \le n$），表示第 $i$ 次操作的参数。

保证所有测试数据中 $n$ 的总和不超过 $10^6$，所有测试数据中 $q$ 的总和不超过 $300\,000$。

输出格式

输出 $q+1$ 个数：第一个数为初始图画的潜能，其余分别为每次操作后图画的潜能。

2
3 4 5
1 1
2
3
2
3
3
9 4 8
1 2 2 1 5 5 1 8
9
8
3
5
4
3
9
8

12
4
4
4
12
4
96
48
48
24
12
12
12
12
36

提示

子任务

定义树的高度为从根到其他顶点的简单路径上的最大边数。

子任务	分数	$n$	$k$	$q$	额外限制	依赖子任务
1	6	$n = 3$	$k \le 4$	$q \le 10$	$t \le 100$，$p_2 = p_3 = 1$
2	9	$\sum n \le 1\,000$	--	$q = 0$	$p_{i} = 2 \cdot \lfloor \frac{i}{2} \rfloor - 1$，$n$ 为奇数
3	10			$\sum q \le 1\,000$	$p_i = 1$	1
4		$n \le 9$	$k \le 4$	$q = 0$	$t \le 100$
5	3			$q \le 10$		4
6	2	$\sum n \le 1\,000$	$k=2$	$q = 0$	--
7	11		--			2, 4, 6
8	15			$\sum q \le 1\,000$		1–7
9	4	$\sum n \le 5\,000$		$\sum q \le 5\,000$		1–8
10	3	$\sum n \le 10\,000$		$\sum q \le 10\,000$		1–9
11	6	$\sum n \le 100\,000$		$\sum q \le 5\,000$
12	7			$\sum q \le 100\,000$	高度不超过 $20$	1, 4, 5
13	14				--	1–12
14	3	$\sum n \le 300\,000$		$\sum q \le 300\,000$		1–13
15		$\sum n \le 1\,000\,000$				1–14

翻译由 DeepSeek V4 Pro 完成