Ildar a décidé de se lancer dans l’art abstrait. Comme base de son tableau, il a pris un arbre enraciné à $n$ sommets : un graphe sans cycle, où le sommet numéro 1 est désigné comme racine. La racine n’a pas de parent, et pour tout autre sommet $u \ge 2$, le premier sommet sur le chemin de $u$ à la racine est appelé le parent du sommet $u$, noté $p_u$. Les sommets dont le parent est le sommet $v$ sont appelés les enfants du sommet $v$. Si un sommet n’a pas d’enfant, il est appelé une feuille. Il est garanti que la racine a au moins deux enfants.

Effectuons un parcours en profondeur (DFS) de l’arbre : nous visitons la racine, puis nous visitons récursivement les sous-arbres de ses enfants un par un de la même manière. Les sommets de l’arbre sont numérotés dans l’ordre de ce parcours en profondeur. Ainsi, pour chaque $i$ de 1 à $n$, les numéros des sommets dans le sous-arbre du sommet $i$ forment un ensemble d’entiers consécutifs.

Supposons que l’arbre a $m$ feuilles. Ildar a écrit leurs numéros dans l’ordre croissant, obtenant une suite de nombres $l_1 < l_2 < \dots < l_m$, et a relié par une arête toutes les paires de feuilles de la forme $(l_j, l_{j+1})$, et a également relié les sommets $l_m$ et $l_1$. Le cycle $l_1 \to l_2 \to \dots \to l_m \to l_1$ ajouté au graphe est appelé le cycle extérieur.

Ildar a dessiné le graphe résultant sur un plan de la manière suivante : il a représenté le cycle extérieur par un cercle, le long duquel les feuilles $l_1, l_2, \dots, l_m$ sont placées dans le sens anti-horaire, et les arcs du cercle entre les sommets adjacents représentent les arêtes du cycle extérieur. Les autres sommets de l’arbre sont représentés par des points distincts situés à l’intérieur de ce cercle. Les arêtes de l’arbre sont représentées par des segments entre les sommets, et les sommets et les arêtes sont positionnés de sorte que les segments des arêtes n’aient pas de points intérieurs communs. La figure ci-dessous montre un exemple de dessin d’arbre.

Dans le dessin d’Ildar, la partie du plan à l’intérieur du cercle du cycle extérieur est divisée en $m$ régions délimitées par les arêtes du graphe. Nous appellerons ces régions des faces. Nous dirons que deux faces distinctes sont adjacentes si elles partagent une arête commune. Par exemple, dans la figure ci-dessus, il y a 5 faces, notons-les $\Gamma_1, \Gamma_2, \Gamma_3, \Gamma_4$ et $\Gamma_5$.

Les faces adjacentes dans la figure ci-dessus sont les paires de faces $(\Gamma_1, \Gamma_2)$, $(\Gamma_1, \Gamma_5)$, $(\Gamma_2, \Gamma_3)$, $(\Gamma_2, \Gamma_4)$, $(\Gamma_2, \Gamma_5)$, $(\Gamma_3, \Gamma_4)$ et $(\Gamma_4, \Gamma_5)$.

Pour terminer son tableau, Ildar prévoit de colorier chaque face avec l’une de $k$ couleurs. Une coloration est dite correcte si les faces adjacentes sont coloriées avec des couleurs différentes. Ildar appelle le potentiel de son dessin le reste de la division du nombre de colorations correctes différentes par $10^9 + 7$.

Après avoir évalué le potentiel du dessin initial, Ildar effectue $q$ opérations sur les arêtes du graphe dessiné. Considérons la $i$-ième opération, spécifiée par un nombre $v_i$ et effectuée sur l’arête de l’arbre reliant les sommets $v_i$ et $p_{v_i}$. Si cette arête est actuellement dessinée sur la figure, Ildar la supprime du dessin ; si cette arête est absente du dessin, il la dessine à nouveau. Après chaque changement, l’ensemble des faces du dessin peut changer : deux faces peuvent fusionner lorsqu’une arête est supprimée, ou une face peut se diviser en deux lorsqu’une arête est dessinée. Par exemple, si l’on supprime l’arête $8 - 9$ dans la figure ci-dessus, alors les faces $\Gamma_4$ et $\Gamma_5$ fusionnent en une seule face $\Gamma_{4+5}$.

Maintenant, les paires de faces adjacentes du dessin sont $(\Gamma_1, \Gamma_2)$, $(\Gamma_1, \Gamma_{4+5})$, $(\Gamma_2, \Gamma_3)$, $(\Gamma_2, \Gamma_{4+5})$ et $(\Gamma_3, \Gamma_{4+5})$.

Après chaque opération, il faut déterminer à nouveau le potentiel du dessin : le reste de la division du nombre de colorations correctes des faces avec au plus $k$ couleurs par $10^9 + 7$.

Entrée

La première ligne de l’entrée contient un entier $t$ ($1 \le t \le 10\,000$) — le nombre de scénarios de test. Vient ensuite la description de $t$ scénarios de test.

La première ligne de chaque scénario de test contient trois entiers $n$, $k$ et $q$ ($3 \le n \le 10^6$, $2 \le k \le 10^9$, $0 \le q \le 300\,000$) — le nombre de sommets de l’arbre, le nombre de couleurs disponibles et le nombre d’opérations effectuées, respectivement.

La deuxième ligne de chaque scénario de test contient les nombres $p_2, p_3, \dots, p_n$ ($1 \le p_i < i$), où $p_i$ est le parent du sommet $i$ dans l’arbre. Il est garanti que les sommets de l’arbre sont numérotés dans l’ordre d’un parcours en profondeur et que la valeur 1 apparaît au moins deux fois parmi les valeurs $p_2, \dots, p_n$.

Viennent ensuite $q$ lignes, la $i$-ième contenant le nombre $v_i$ ($2 \le v_i \le n$) — le paramètre de la $i$-ième opération.

Il est garanti que la somme des $n$ sur tous les scénarios de test ne dépasse pas $10^6$.

Il est garanti que la somme des $q$ sur tous les scénarios de test ne dépasse pas $300\,000$.

Sortie

Pour chaque scénario de test, affichez $q + 1$ entiers ; le premier doit être égal au potentiel du dessin initial, et les suivants doivent être égaux au potentiel du dessin après chaque opération.

Sous-tâches

Nous définissons la hauteur d’un arbre comme le nombre maximum d’arêtes sur un chemin simple de la racine à tout autre sommet.

Exemples

Entrée 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

Sortie 1

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