Ildar は抽象芸術に取り組むことにした。彼は絵画の基礎として、$n$ 個の頂点を持つ根付き木 (サイクルのないグラフ) を用意した。ここで頂点 1 が根と指定されている。根には親がなく、任意の他の頂点 $u \ge 2$ について、$u$ から根への経路上の最初の頂点を頂点 $u$ の親と呼び、$p_u$ で表す。頂点 $v$ を親にもつ頂点を頂点 $v$ の子と呼ぶ。子を持たない頂点を葉と呼ぶ。根には少なくとも 2 つの子があることが保証される。
木の深さ優先探索 (DFS) を実行する: 根を訪れ、次にその子の部分木を同様の方法で順に再帰的に訪れる。木の頂点はこの深さ優先探索の順序で番号付けされる。したがって、$i$ が $1$ から $n$ までの各 $i$ について、頂点 $i$ の部分木内の頂点番号は連続する整数の集合をなす。
木に $m$ 個の葉があるとする。Ildar はそれらの番号を昇順に書き並べ、数列 $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$ は 外側のサイクル と呼ばれる。
Ildar は得られたグラフを平面上に次のように描いた: 外側のサイクルを円として表現し、葉 $l_1, l_2, \dots, l_m$ が反時計回りに配置され、隣接する頂点間の円弧が外側のサイクルの辺を表す。木の残りの頂点はこの円の内部にある異なる点として表される。木の辺は頂点間の線分として表され、頂点と辺は、辺の線分が共通の内部点を持たないように配置される。下図は木の描画の例である。
Ildar の描画では、外側のサイクルの円の内側の平面部分は、グラフの辺によって囲まれた $m$ 個の領域に分割される。これらの領域を 面 と呼ぶ。異なる2つの面が共通の辺を共有するとき、それらは 隣接している と呼ぶ。例えば、上の図には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)$ である。
絵を完成させるために、Ildar は各面を $k$ 色のいずれかで彩色する予定である。彩色が 正しい とは、隣接する面が異なる色で彩色されていることをいう。Ildar は自分の描画の ポテンシャル を、異なる正しい彩色の数を $10^9+7$ で割った余りと定義する。
初期の描画のポテンシャルを評価した後、Ildar は描画されたグラフの辺に対して $q$ 回の操作を行う。$i$ 番目の操作を考える。この操作は数 $v_i$ で指定され、頂点 $v_i$ と $p_{v_i}$ を結ぶ木の辺に対して行われる。この辺が現在図に描かれていれば、Ildar はその辺を図から取り除く。描かれていなければ、再び描く。各変更の後、図の面の集合は変化しうる: 辺を取り除くときは2つの面が融合し、辺を描くときは1つの面が2つに分割される。例えば、上の図で辺 $8-9$ を取り除くと、面 $\Gamma_4$ と $\Gamma_5$ が1つの面 $\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$ 個のテストケースの説明が続く。
各テストケースの最初の行には、3 つの整数 $n$, $k$, $q$ ($3 \le n \le 10^6$, $2 \le k \le 10^9$, $0 \le q \le 300\,000$) が含まれる — 木の頂点数、使用可能な色の数、実行される操作の数。
各テストケースの 2 行目には、$p_2, p_3, \dots, p_n$ ($1 \le p_i < i$) が含まれる。ここで $p_i$ は木における頂点 $i$ の親である。木の頂点は深さ優先探索の順序で番号付けされており、また値 $p_2, \dots, p_n$ の中に 1 が少なくとも 2 回出現することが保証される。
その後、$q$ 行が続き、$i$ 行目には操作のパラメータである数 $v_i$ ($2 \le v_i \le n$) が含まれる。
すべてのテストケースにわたる $n$ の総和が $10^6$ を超えないことが保証される。
すべてのテストケースにわたる $q$ の総和が $300\,000$ を超えないことが保証される。
出力
各テストケースについて、$q+1$ 個の整数を出力せよ。最初の整数は初期の描画のポテンシャル、残りは各操作後の描画のポテンシャルでなければならない。
小課題
木の高さを、根から他の任意の頂点への単純パス上の最大辺数と定義する。
| 小課題 | 得点 | $n$ | $k$ | $q$ | 追加制約 | 必須小課題 |
|---|---|---|---|---|---|---|
| 1 | 6 | $n = 3$ | $k \le 4$ | $q \le 10$ | $t \le 100$, $p_2 = p_3 = 1$ | |
| 2 | 9 | $\sum n \le 1000$ | $q = 0$ | $p_i = 2 \cdot \lfloor \frac{i}{2} \rfloor - 1$, $n$ は奇数 | ||
| 3 | 10 | $\sum n \le 1000$ | $\sum q \le 1000$ | $p_i = 1$ | 1 | |
| 4 | 4 | $n \le 9$ | $k \le 4$ | $q = 0$ | $t \le 100$ | |
| 5 | 3 | $n \le 9$ | $k \le 4$ | $q \le 10$ | $t \le 100$ | Self, 4 |
| 6 | 2 | $\sum n \le 1000$ | $k = 2$ | $q = 0$ | ||
| 7 | 11 | $\sum n \le 1000$ | $q = 0$ | 2, 4, 6 | ||
| 8 | 15 | $\sum n \le 1000$ | $\sum q \le 1000$ | Self, 1–7 | ||
| 9 | 4 | $\sum n \le 5000$ | $\sum q \le 5000$ | Self, 1–8 | ||
| 10 | 3 | $\sum n \le 10\,000$ | $\sum q \le 10\,000$ | Self, 1–9 | ||
| 11 | 6 | $\sum n \le 100\,000$ | $\sum q \le 5000$ | Self, 1–9 | ||
| 12 | 7 | $\sum n \le 100\,000$ | $\sum q \le 100\,000$ | 高さ 20 以下 | Self, 1, 4, 5 | |
| 13 | 14 | $\sum n \le 100\,000$ | $\sum q \le 100\,000$ | Self, 1–12 | ||
| 14 | 3 | $\sum n \le 300\,000$ | $\sum q \le 300\,000$ | Self, 1–13 | ||
| 15 | 3 | $\sum n \le 1\,000\,000$ | $\sum q \le 300\,000$ | Self, 1–14 |
入出力例
入力 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