Ildar 决定从事抽象艺术创作。作为画作的基础，他选择了一棵有 $n$ 个顶点的有根树：一个无环图，其中顶点 1 被指定为根。根没有父节点，对于任意其他顶点 $u \ge 2$，从 $u$ 到根的路径上的第一个顶点称为顶点 $u$ 的父节点，记作 $p_u$。父节点为 $v$ 的顶点称为 $v$ 的子节点。如果一个顶点没有子节点，则称为叶子。保证根至少有两个子节点。
让我们对这棵树执行深度优先搜索（DFS）：先访问根，然后按相同的方式递归访问其每个子节点的子树。树的顶点按照此次深度优先搜索的顺序编号。因此，对于每个 $i$ 从 1 到 $n$，顶点 $i$ 子树中的顶点编号构成一组连续的整数。
假设树有 $m$ 个叶子。Ildar 将它们按递增顺序写下，得到序列 $l_1 < l_2 < \dots < l_m$，然后连接所有形如 $(l_j, l_{j+1})$ 的叶子对，同时连接 $l_m$ 和 $l_1$。添加到图中的环 $l_1 \to l_2 \to \dots \to l_m \to l_1$ 称为外环。
Ildar 将得到的图在平面上绘制如下：他将外环画成一个圆，叶子 $l_1, l_2, \dots, l_m$ 沿圆逆时针排列，圆上相邻顶点之间的弧表示外环的边。树的其他顶点用位于该圆内部的不同点表示。树的边用顶点之间的线段表示，并且顶点和边的位置使得边线段之间没有公共内点。下图展示了一个树的绘制示例。
在 Ildar 的画作中，外环圆内部的平面部分被图的边划分为 $m$ 个区域。我们将这些区域称为面。如果两个不同的面共享一条公共边，则称它们相邻。例如，上图中一共有 5 个面，我们将其记为 $\Gamma_1, \Gamma_2, \Gamma_3, \Gamma_4$ 和 $\Gamma_5$。
上图中相邻的面有 $(\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)$。
为了完成画作，Ildar 计划用 $k$ 种颜色中的一种给每个面染色。如果一个染色方案中相邻的面颜色不同，则称之为合法染色。Ildar 将他的画作的潜力定义为合法染色方案数除以 $10^9 + 7$ 的余数。
在评估初始画作的潜力之后，Ildar 对已绘制图的边执行 $q$ 次操作。考虑第 $i$ 次操作，由数字 $v_i$ 指定，作用于连接顶点 $v_i$ 和 $p_{v_i}$ 的树边。如果这条边当前在图中，Ildar 将其从图中移除；如果这条边不在图中，则重新绘制它。每次更改后，图中的面集可能会发生变化：移除一条边时两个面可能合并，或者绘制一条边时一个面可能分裂为两个。例如，在上图中移除边 $8 - 9$ 后，面 $\Gamma_4$ 和 $\Gamma_5$ 将合并为一个面 $\Gamma_{4+5}$。
此时图中相邻的面为 $(\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, \dots, p_n$ ($1 \le p_i < i$)，其中 $p_i$ 是树中顶点 $i$ 的父节点。保证树的顶点按照深度优先搜索的顺序编号，且在 $p_2, \dots, p_n$ 中，值 1 至少出现两次。
接下来有 $q$ 行，第 $i$ 行包含数字 $v_i$ ($2 \le v_i \le n$) — 第 $i$ 次操作的参数。
保证所有测试用例的 $n$ 之和不超过 $10^6$。
保证所有测试用例的 $q$ 之和不超过 $300\,000$。
输出格式
对于每个测试用例，输出 $q + 1$ 个整数，第一个必须等于初始画作的潜力，其余必须等于每次操作后画作的潜力。
子任务
定义树的高度为从根到任意其他顶点的简单路径上边的最大数量。
| 子任务 | 分数 | $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 1000$ | $q = 0$ | $p_i = 2 \cdot \lfloor \frac{i}{2} \rfloor - 1$，$n$ 为奇数 | ||
| 3 | 10 | $\sum n \le 1000$ | $\sum q \le 1000$ | $p_i = 1$ | 1 | |
| 4 | 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 10\,000$ | $\sum q \le 10\,000$ | 自身, 1–9 | ||
| 11 | 6 | $\sum n \le 100\,000$ | $\sum q \le 5000$ | 自身, 1–9 | ||
| 12 | 7 | $\sum n \le 100\,000$ | $\sum q \le 100\,000$ | 高度至多 20 | 自身, 1, 4, 5 | |
| 13 | 14 | $\sum n \le 100\,000$ | $\sum q \le 100\,000$ | 自身, 1–12 | ||
| 14 | 3 | $\sum n \le 300\,000$ | $\sum q \le 300\,000$ | 自身, 1–13 | ||
| 15 | 3 | $\sum n \le 1\,000\,000$ | $\sum q \le 300\,000$ | 自身, 1–14 |
样例
样例输入 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
样例输出 1
12 4 4 4 12 4 96 48 48 24 12 12 12 12 36