Ildar decidió dedicarse al arte abstracto. Como base para su pintura, tomó un árbol enraizado con $n$ vértices: un grafo sin ciclos, donde el vértice número $1$ está designado como la raíz. La raíz no tiene padre, y para cualquier otro vértice $u \ge 2$, el primer vértice en el camino desde $u$ hasta la raíz se llama el padre del vértice $u$, denotado como $p_u$. Los vértices cuyo padre es el vértice $v$ se llaman hijos del vértice $v$. Si un vértice no tiene hijos, se llama hoja. Está garantizado que la raíz tiene al menos dos hijos.

Realicemos una búsqueda en profundidad (DFS) del árbol: visitamos la raíz, y luego visitamos recursivamente los subárboles de sus hijos uno por uno de la misma manera. Los vértices del árbol se numeran en el orden de esta búsqueda en profundidad. Así, para cada $i$ desde $1$ hasta $n$, los números de los vértices en el subárbol del vértice $i$ forman un conjunto de enteros consecutivos.

Supongamos que el árbol tiene $m$ hojas. Ildar escribió sus números en orden creciente, obteniendo una secuencia de números $l_1 < l_2 < \dots < l_m$, y conectó con una arista todos los pares de hojas de la forma $(l_j, l_{j+1})$, y también conectó los vértices $l_m$ y $l_1$. El ciclo $l_1 \to l_2 \to \dots \to l_m \to l_1$ añadido al grafo se llama el ciclo exterior.

Ildar dibujó el grafo resultante en un plano de la siguiente manera: representó el ciclo exterior como un círculo, a lo largo del cual las hojas $l_1, l_2, \dots, l_m$ están ubicadas en sentido antihorario, y los arcos del círculo entre vértices adyacentes representan las aristas del ciclo exterior. Los vértices restantes del árbol se representan como puntos distintos ubicados dentro de este círculo. Las aristas del árbol se representan como segmentos entre vértices, y los vértices y aristas están posicionados de tal manera que los segmentos de las aristas no tienen puntos interiores comunes. La figura siguiente muestra un ejemplo de un dibujo de árbol.

En el dibujo de Ildar, la parte del plano dentro del círculo del ciclo exterior está dividida en $m$ regiones delimitadas por las aristas del grafo. Llamaremos a estas regiones caras. Llamaremos a dos caras distintas adyacentes si comparten una arista común. Por ejemplo, en la figura anterior hay $5$ caras, denotémoslas como $\Gamma_1, \Gamma_2, \Gamma_3, \Gamma_4$ y $\Gamma_5$.

Las caras adyacentes en la figura anterior son los pares de caras $(\Gamma_1, \Gamma_2)$, $(\Gamma_1, \Gamma_5)$, $(\Gamma_2, \Gamma_3)$, $(\Gamma_2, \Gamma_4)$, $(\Gamma_2, \Gamma_5)$, $(\Gamma_3, \Gamma_4)$ y $(\Gamma_4, \Gamma_5)$.

Para completar su pintura, Ildar planea colorear cada cara en uno de $k$ colores. Una coloración se llama correcta si las caras adyacentes están coloreadas con colores diferentes. Ildar llama potencial de su dibujo al resto de la división del número de coloraciones correctas diferentes entre $10^9 + 7$.

Después de evaluar el potencial del dibujo inicial, Ildar realiza $q$ operaciones con las aristas del grafo dibujado. Considere la $i$-ésima operación, que está especificada por un número $v_i$ y se realiza sobre la arista del árbol que conecta los vértices $v_i$ y $p_{v_i}$. Si esta arista está actualmente dibujada en la figura, Ildar elimina esta arista del dibujo; si la arista está ausente del dibujo, se dibuja nuevamente. Después de cada cambio, el conjunto de caras en el dibujo puede cambiar: dos caras pueden fusionarse cuando se elimina una arista, o una cara puede dividirse en dos cuando se dibuja una arista. Por ejemplo, si eliminamos la arista $8 - 9$ en la figura anterior, entonces las caras $\Gamma_4$ y $\Gamma_5$ se fusionarán en una sola cara $\Gamma_{4+5}$.

Ahora, los pares de caras adyacentes en el dibujo son $(\Gamma_1, \Gamma_2)$, $(\Gamma_1, \Gamma_{4+5})$, $(\Gamma_2, \Gamma_3)$, $(\Gamma_2, \Gamma_{4+5})$ y $(\Gamma_3, \Gamma_{4+5})$.

Después de realizar cada operación, es necesario determinar nuevamente el potencial del dibujo: el resto de la división del número de coloraciones correctas de las caras en a lo sumo $k$ colores entre $10^9 + 7$.

Entrada

La primera línea de la entrada contiene un entero $t$ ($1 \le t \le 10\,000$) — el número de casos de prueba. Luego sigue la descripción de $t$ casos de prueba.

La primera línea de cada caso de prueba contiene tres enteros $n$, $k$ y $q$ ($3 \le n \le 10^6$, $2 \le k \le 10^9$, $0 \le q \le 300\,000$) — el número de vértices en el árbol, el número de colores disponibles y el número de operaciones realizadas, respectivamente.

La segunda línea de cada caso de prueba contiene los números $p_2, p_3, \dots, p_n$ ($1 \le p_i < i$), donde $p_i$ es el padre del vértice $i$ en el árbol. Está garantizado que los vértices del árbol están numerados en el orden de una búsqueda en profundidad y que el valor $1$ aparece al menos dos veces entre los valores $p_2, \dots, p_n$.

Luego siguen $q$ líneas, la $i$-ésima de las cuales contiene el número $v_i$ ($2 \le v_i \le n$) — el parámetro de la $i$-ésima operación.

Está garantizado que la suma de $n$ sobre todos los casos de prueba no excede $10^6$.

Está garantizado que la suma de $q$ sobre todos los casos de prueba no excede $300\,000$.

Salida

Para cada caso de prueba, imprime $q + 1$ enteros, el primero de los cuales debe ser igual al potencial del dibujo inicial, y el resto debe ser igual al potencial del dibujo después de realizar cada operación.

Subtareas

Definimos la altura de un árbol como el número máximo de aristas en un camino simple desde la raíz hasta cualquier otro vértice.

Ejemplos

Entrada 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

Salida 1

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