题目描述

伊尔达尔决定从事抽象艺术。他以一棵有根树作为画作基础。树有 $n$ 个顶点，编号为 $1$ 到 $n$，其中顶点 $1$ 是根。

根没有父亲；对于任意其他顶点 $u\ge 2$，从 $u$ 到根的路径上的第一个顶点称为 $u$ 的父亲，记为 $p_u$。父亲为 $v$ 的顶点称为 $v$ 的儿子。没有儿子的顶点称为叶子。保证根至少有两个儿子。

对这棵树进行深度优先遍历：先访问根，然后按顺序递归访问其各个儿子的子树。树中顶点已经按照这次 DFS 的访问顺序编号。因此，对于任意顶点 $i$，它的子树中所有顶点的编号构成一段连续整数。

设树中共有 $m$ 个叶子。伊尔达尔按编号递增顺序写下这些叶子的编号，得到

$$l_1<l_2<\cdots<l_m。$$

然后他添加边连接所有形如 $(l_j,l_{j+1})$ 的叶子对，并额外连接 $l_m$ 与 $l_1$。添加得到的环

$$l_1\to l_2\to\cdots\to l_m\to l_1$$

称为外环。

伊尔达尔把所得图画在平面上：外环画成一个圆，叶子 $l_1,l_2,\ldots,l_m$ 按逆时针方向位于圆周上，相邻叶子之间的圆弧表示外环的边。树中其他顶点画在圆内，树边画成连接顶点的线段，并且顶点和边的位置满足边段之间没有公共内点。

这样，外环内部的平面区域被图划分成 $m$ 个区域，这些区域称为面。若两个不同的面有公共边，则称它们相邻。

题面中的第一幅图给出了一个树的绘制示例；第二幅图中将其中 $5$ 个面标记为 $\Gamma_1,\Gamma_2,\Gamma_3,\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}$，相邻关系也会随之改变。

在初始状态以及每次操作后，都需要求出当前图的势能。

输入格式

第一行包含一个整数 $t$（$1\le t\le 10000$），表示测试数据组数。

接下来依次给出 $t$ 组数据。

每组数据第一行包含三个整数 $n,k,q$：

$$3\le n\le 10^6, \qquad 2\le k\le 10^9, \qquad 0\le q\le 300\,000。$$

第二行包含 $p_2,p_3,\ldots,p_n$，其中 $p_i$ 是顶点 $i$ 的父亲，满足

$$1\le p_i<i。$$

保证顶点编号为 DFS 顺序，并且在 $p_2,p_3,\ldots,p_n$ 中，数值 $1$ 至少出现两次，即根至少有两个儿子。

接下来 $q$ 行，第 $i$ 行包含一个整数 $v_i$（$2\le v_i\le n$），表示第 $i$ 次操作切换树边 $(v_i,p_{v_i})$ 的存在状态。

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

输出格式

对每组数据，输出 $q+1$ 个数：

• 第一个数为初始图的势能；
• 接下来第 $i$ 个数为执行第 $i$ 次操作后的势能。

每个数单独占一行。

样例

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

子任务与评分

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

子任务	分值	附加限制	必要子任务
1	6	$n=3,\ k\le 4,\ q\le 10,\ t\le 100,\ p_2=p_3=1$	-
2	9	$\sum n\le 1000,\ q=0,\ p_i=2\lfloor i/2\rfloor-1,\ n$ 为奇数
3	10	$\sum n\le 1000,\sum q\le 1000,\ p_i=1$	1
4		$n\le 9,\ k\le 4,\ q=0,\ t\le 100$	-
5	3	$n\le 9,\ k\le 4,\ q\le 10,\ t\le 100$	样例，4
6	2	$\sum n\le 1000,\ k=2,\ q=0$	-
7	11	$\sum n\le 1000,\ q=0$	2，4，6
8	15	$\sum n\le 1000,\sum q\le 1000$	样例，1-7
9	4	$\sum n\le 5000,\sum q\le 5000$	样例，1-8
10	3	$\sum n\le 10000,\sum q\le 10000$	样例，1-9
11	6	$\sum n\le 100000,\sum q\le 5000$
12	7	$\sum n\le 100000,\sum q\le 100000$，树高不超过 $20$	样例，1，4，5
13	14	$\sum n\le 100000,\sum q\le 100000$	样例，1-12
14	3	$\sum n\le 300000,\sum q\le 300000$	样例，1-13
15		$\sum n\le 1000000,\sum q\le 300000$	样例，1-14