일랴르는 추상 미술에 도전하기로 했다. 그는 그림의 기초로 $n$개의 정점을 가진 루트 트리, 즉 사이클이 없는 그래프를 사용했다. 여기서 정점 1번이 루트로 지정된다. 루트는 부모가 없으며, 다른 모든 정점 $u \ge 2$에 대해 $u$에서 루트로 가는 경로의 첫 번째 정점을 정점 $u$의 부모라고 하며 $p_u$로 표기한다. 어떤 정점 $v$를 부모로 가지는 정점들을 $v$의 자식이라고 한다. 자식이 없는 정점은 잎 노드라고 부른다. 루트는 적어도 두 개의 자식을 가짐이 보장된다.

트리의 깊이 우선 탐색(DFS)을 수행해 보자. 루트를 방문한 후, 자식들의 서브트리를 같은 방식으로 하나씩 재귀적으로 방문한다. 트리의 정점들은 이 깊이 우선 탐색 순서대로 번호가 매겨진다. 따라서 $1$부터 $n$까지의 각 $i$에 대해, 정점 $i$의 서브트리에 있는 정점 번호들은 연속된 정수 집합을 이룬다.

트리에 $m$개의 잎 노드가 있다고 가정하자. 일랴르는 이 잎 노드들의 번호를 증가하는 순서대로 적어 $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$을 외부 사이클이라고 부른다.

일랴르는 결과 그래프를 평면에 다음과 같이 그렸다. 외부 사이클을 원으로 나타내고, 잎 노드 $l_1, l_2, \dots, l_m$이 반시계 방향으로 원 위에 배치되며, 인접한 정점 사이의 원호는 외부 사이클의 간선을 나타낸다. 트리의 나머지 정점들은 이 원 내부에 위치한 서로 다른 점으로 표현된다. 트리 간선들은 정점 사이의 선분으로 표현되며, 정점과 간선들은 간선 선분들이 공통 내부 점을 가지지 않도록 배치된다. 아래 그림은 트리 그림의 예시를 보여준다.

일랴르의 그림에서 외부 사이클 원 내부의 평면 부분은 그래프 간선들로 둘러싸인 $m$개의 영역으로 나뉜다. 이 영역들을 면(face)이라고 부르자. 서로 다른 두 면이 공통 간선을 공유할 때 인접하다고 부른다. 예를 들어, 위 그림에는 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)$이다.

그림을 완성하기 위해 일랴르는 각 면을 $k$가지 색 중 하나로 색칠할 계획이다. 인접한 면이 서로 다른 색으로 칠해진 경우를 올바른 색칠이라고 한다. 일랴르는 자신의 그림의 잠재력을 올바른 색칠의 개수를 $10^9+7$로 나눈 나머지라고 부른다.

초기 그림의 잠재력을 계산한 후, 일랴르는 그려진 그래프의 간선에 대해 $q$개의 연산을 수행한다. $i$번째 연산은 정점 $v_i$로 지정되며, 정점 $v_i$와 $p_{v_i}$를 연결하는 트리 간선에 대해 수행된다. 만약 이 간선이 현재 그림에 그려져 있다면 일랴르는 이 간선을 그림에서 제거하고, 그림에 없었다면 다시 그린다. 각 변경 후, 그림의 면 집합이 바뀔 수 있다. 간선이 제거되면 두 면이 합쳐지거나, 간선이 그려지면 하나의 면이 두 개로 나뉠 수 있다. 예를 들어, 위 그림에서 $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$개의 정수를 출력한다. 첫 번째 정수는 초기 그림의 잠재력이어야 하며, 나머지는 각 연산을 수행한 후의 그림의 잠재력이어야 한다.

서브태스크

트리의 높이를 루트에서 다른 정점까지의 단순 경로에 있는 간선의 최대 개수로 정의한다.

예제

입력 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