Ильдар решил заняться абстрактной живописью. В качестве основы для своей картины он взял корневое дерево с $n$ вершинами: граф без циклов, где вершина номер 1 обозначена корнем. У корня нет родителя, а для любой другой вершины $u \ge 2$ первая вершина на пути от $u$ до корня называется родителем вершины $u$ и обозначается $p_u$. Вершины, у которых родителем является вершина $v$, называются детьми вершины $v$. Если вершина не имеет детей, она называется листом. Гарантируется, что у корня есть хотя бы два ребенка.

Выполним обход дерева в глубину (DFS): посещаем корень, а затем рекурсивно обходим поддеревья его детей одно за другим в том же порядке. Вершины дерева нумеруются в порядке этого обхода в глубину. Таким образом, для каждого $i$ от 1 до $n$ номера вершин в поддереве вершины $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$ областей, ограниченных ребрами графа. Эти области будем называть гранями. Две различные грани будем называть смежными, если они имеют общее ребро. Например, на рисунке выше 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