Ildar decided to take up abstract art. As the basis for his painting, he took a rooted tree with $n$ vertices: a graph without cycles, where vertex number 1 is designated as the root. The root has no parent, and for any other vertex $u \ge 2$, the first vertex on the path from $u$ to the root is called the parent of vertex $u$, denoted as $p_u$. Vertices whose parent is vertex $v$ are called children of vertex $v$. If a vertex has no children, it is called a leaf. It is guaranteed that the root has at least two children.

Let's perform a depth-first search (DFS) of the tree: we visit the root, and then recursively visit the subtrees of its children one by one in the same manner. The vertices of the tree are numbered in the order of this depth-first search. Thus, for each $i$ from 1 to $n$, the vertex numbers in the subtree of vertex $i$ form a set of consecutive integers.

Suppose the tree has $m$ leaves. Ildar wrote down their numbers in increasing order, obtaining a sequence of numbers $l_1 < l_2 < \dots < l_m$, and connected with an edge all pairs of leaves of the form $(l_j, l_{j+1})$, and also connected vertices $l_m$ and $l_1$. The cycle $l_1 \to l_2 \to \dots \to l_m \to l_1$ added to the graph is called the outer cycle.

Ildar drew the resulting graph on a plane as follows: he represented the outer cycle as a circle, along which the leaves $l_1, l_2, \dots, l_m$ are located counterclockwise, and the arcs of the circle between adjacent vertices represent the edges of the outer cycle. The remaining vertices of the tree are represented as distinct points located inside this circle. The tree edges are represented as segments between vertices, and the vertices and edges are positioned in such a way that the segments of the edges do not have common internal points. The figure below shows an example of a tree drawing.

In Ildar's drawing, the part of the plane inside the circle of the outer cycle is divided into $m$ regions bounded by the edges of the graph. We will call these regions faces. We will call two distinct faces adjacent if they share a common edge. For example, in the figure above, there are 5 faces, let's denote them as $\Gamma_1, \Gamma_2, \Gamma_3, \Gamma_4$, and $\Gamma_5$.

Adjacent faces in the figure above are the pairs of 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)$, and $(\Gamma_4, \Gamma_5)$.

To complete his painting, Ildar plans to color each face in one of $k$ colors. A coloring is called correct if adjacent faces are colored in different colors. Ildar calls the potential of his drawing the remainder of the division of the number of different correct colorings by $10^9 + 7$.

After evaluating the potential of the initial drawing, Ildar performs $q$ operations with the edges of the drawn graph. Consider the $i$-th operation, which is specified by a number $v_i$ and is performed on the tree edge connecting vertices $v_i$ and $p_{v_i}$. If this edge is currently drawn on the figure, Ildar removes this edge from the drawing; if this edge is absent from the drawing, it is drawn again. After each change, the set of faces in the drawing may change: two faces may merge when an edge is removed, or one face may split into two when an edge is drawn. For example, if we remove the edge $8 - 9$ in the figure above, then faces $\Gamma_4$ and $\Gamma_5$ will merge into a single face $\Gamma_{4+5}$.

Now, the adjacent pairs of faces in the drawing are $(\Gamma_1, \Gamma_2)$, $(\Gamma_1, \Gamma_{4+5})$, $(\Gamma_2, \Gamma_3)$, $(\Gamma_2, \Gamma_{4+5})$, and $(\Gamma_3, \Gamma_{4+5})$.

After performing each operation, it is necessary to determine the potential of the drawing again: the remainder of the division of the number of correct colorings of the faces in at most $k$ colors by $10^9 + 7$.

Input

The first line of the input contains an integer $t$ ($1 \le t \le 10\,000$) — the number of test cases. Then follows the description of $t$ test cases.

The first line of each test case contains three integers $n$, $k$, and $q$ ($3 \le n \le 10^6$, $2 \le k \le 10^9$, $0 \le q \le 300\,000$) — the number of vertices in the tree, the number of available colors, and the number of operations performed, respectively.

The second line of each test case contains the numbers $p_2, p_3, \dots, p_n$ ($1 \le p_i < i$), where $p_i$ is the parent of vertex $i$ in the tree. It is guaranteed that the vertices of the tree are numbered in the order of a depth-first search and that the value 1 appears at least twice among the values $p_2, \dots, p_n$.

Then follow $q$ lines, the $i$-th of which contains the number $v_i$ ($2 \le v_i \le n$) — the parameter of the $i$-th operation.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^6$.

It is guaranteed that the sum of $q$ over all test cases does not exceed $300\,000$.

Output

For each test case, output $q + 1$ integers, the first of which must be equal to the potential of the initial drawing, and the rest must be equal to the potential of the drawing after performing each operation.

Subtasks

We define the height of a tree as the maximum number of edges on a simple path from the root to any other vertex.

Examples

Input 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

Output 1

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