Ildar postanowił zająć się sztuką abstrakcyjną. Jako podstawę swojego obrazu wziął ukorzenione drzewo o $n$ wierzchołkach: graf bez cykli, w którym wierzchołek numer 1 jest wyznaczony jako korzeń. Korzeń nie ma rodzica, a dla każdego innego wierzchołka $u \ge 2$ pierwszym wierzchołkiem na ścieżce od $u$ do korzenia jest rodzic wierzchołka $u$, oznaczany jako $p_u$. Wierzchołki, których rodzicem jest wierzchołek $v$, nazywane są dziećmi wierzchołka $v$. Jeśli wierzchołek nie ma dzieci, nazywany jest liściem. Gwarantowane jest, że korzeń ma co najmniej dwoje dzieci.

Wykonajmy przeszukiwanie w głąb (DFS) drzewa: odwiedzamy korzeń, a następnie rekurencyjnie odwiedzamy poddrzewa jego dzieci jedno po drugim w ten sam sposób. Wierzchołki drzewa są numerowane w kolejności tego przeszukiwania w głąb. Zatem dla każdego $i$ od 1 do $n$ numery wierzchołków w poddrzewie wierzchołka $i$ tworzą zbiór kolejnych liczb całkowitych.

Załóżmy, że drzewo ma $m$ liści. Ildar zapisał ich numery w kolejności rosnącej, otrzymując ciąg liczb $l_1 < l_2 < \dots < l_m$, i połączył krawędzią wszystkie pary liści postaci $(l_j, l_{j+1})$, a także połączył wierzchołki $l_m$ i $l_1$. Cykl $l_1 \to l_2 \to \dots \to l_m \to l_1$ dodany do grafu nazywany jest cyklem zewnętrznym.

Ildar narysował otrzymany graf na płaszczyźnie w następujący sposób: przedstawił cykl zewnętrzny jako okrąg, wzdłuż którego liście $l_1, l_2, \dots, l_m$ są umieszczone przeciwnie do ruchu wskazówek zegara, a łuki okręgu między sąsiednimi wierzchołkami reprezentują krawędzie cyklu zewnętrznego. Pozostałe wierzchołki drzewa są przedstawione jako różne punkty znajdujące się wewnątrz tego okręgu. Krawędzie drzewa są przedstawione jako odcinki między wierzchołkami, a wierzchołki i krawędzie są ułożone w taki sposób, że odcinki krawędzi nie mają wspólnych punktów wewnętrznych. Poniższy rysunek przedstawia przykład rysunku drzewa.

Na rysunku Ildara część płaszczyzny wewnątrz okręgu cyklu zewnętrznego jest podzielona na $m$ obszarów ograniczonych krawędziami grafu. Obszary te nazywamy ścianami. Dwie różne ściany nazywamy sąsiednimi, jeśli mają wspólną krawędź. Na przykład na powyższym rysunku znajduje się 5 ścian, oznaczmy je jako $\Gamma_1, \Gamma_2, \Gamma_3, \Gamma_4$ i $\Gamma_5$.

Sąsiednimi ścianami na powyższym rysunku są pary ścian $(\Gamma_1, \Gamma_2)$, $(\Gamma_1, \Gamma_5)$, $(\Gamma_2, \Gamma_3)$, $(\Gamma_2, \Gamma_4)$, $(\Gamma_2, \Gamma_5)$, $(\Gamma_3, \Gamma_4)$ i $(\Gamma_4, \Gamma_5)$.

Aby ukończyć swój obraz, Ildar planuje pokolorować każdą ścianę jednym z $k$ kolorów. Kolorowanie nazywamy poprawnym, jeśli sąsiednie ściany są pokolorowane różnymi kolorami. Ildar nazywa potencjałem swojego rysunku resztę z dzielenia liczby różnych poprawnych kolorowań przez $10^9 + 7$.

Po oszacowaniu potencjału początkowego rysunku Ildar wykonuje $q$ operacji na krawędziach narysowanego grafu. Rozważmy $i$-tą operację, która jest określona przez liczbę $v_i$ i jest wykonywana na krawędzi drzewa łączącej wierzchołki $v_i$ i $p_{v_i}$. Jeśli ta krawędź jest aktualnie narysowana na rysunku, Ildar usuwa tę krawędź z rysunku; jeśli tej krawędzi brakuje na rysunku, rysuje ją ponownie. Po każdej zmianie zbiór ścian na rysunku może się zmienić: dwie ściany mogą się połączyć po usunięciu krawędzi lub jedna ściana może się podzielić na dwie po narysowaniu krawędzi. Na przykład, jeśli usuniemy krawędź $8 - 9$ na powyższym rysunku, to ściany $\Gamma_4$ i $\Gamma_5$ połączą się w jedną ścianę $\Gamma_{4+5}$.

Teraz sąsiednimi parami ścian na rysunku są $(\Gamma_1, \Gamma_2)$, $(\Gamma_1, \Gamma_{4+5})$, $(\Gamma_2, \Gamma_3)$, $(\Gamma_2, \Gamma_{4+5})$ i $(\Gamma_3, \Gamma_{4+5})$.

Po wykonaniu każdej operacji należy ponownie wyznaczyć potencjał rysunku: resztę z dzielenia liczby poprawnych kolorowań ścian w co najwyżej $k$ kolorach przez $10^9 + 7$.

Wejście

Pierwszy wiersz wejścia zawiera liczbę całkowitą $t$ ($1 \le t \le 10\,000$) — liczbę zestawów danych. Następnie znajduje się opis $t$ zestawów danych.

Pierwszy wiersz każdego zestawu danych zawiera trzy liczby całkowite $n$, $k$ i $q$ ($3 \le n \le 10^6$, $2 \le k \le 10^9$, $0 \le q \le 300\,000$) — odpowiednio liczbę wierzchołków w drzewie, liczbę dostępnych kolorów i liczbę wykonanych operacji.

Drugi wiersz każdego zestawu danych zawiera liczby $p_2, p_3, \dots, p_n$ ($1 \le p_i < i$), gdzie $p_i$ jest rodzicem wierzchołka $i$ w drzewie. Gwarantowane jest, że wierzchołki drzewa są ponumerowane w kolejności przeszukiwania w głąb oraz że wartość 1 występuje co najmniej dwa razy wśród wartości $p_2, \dots, p_n$.

Następnie następuje $q$ wierszy, z których $i$-ty zawiera liczbę $v_i$ ($2 \le v_i \le n$) — parametr $i$-tej operacji.

Gwarantowane jest, że suma $n$ po wszystkich zestawach danych nie przekracza $10^6$.

Gwarantowane jest, że suma $q$ po wszystkich zestawach danych nie przekracza $300\,000$.

Wyjście

Dla każdego zestawu danych wypisz $q + 1$ liczb całkowitych, z których pierwsza musi być równa potencjałowi początkowego rysunku, a pozostałe muszą być równe potencjałowi rysunku po wykonaniu każdej operacji.

Podzadania

Definiujemy wysokość drzewa jako maksymalną liczbę krawędzi na prostej ścieżce od korzenia do dowolnego innego wierzchołka.

Przykład

Wejście 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

Wyjście 1

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