P8280 "MCOI-08" Photoelectric Effect.

There is a tree with $n$ ($1 \le n \le 10^5$) nodes and $k$ ($2 \le k \le 5$) colors, with node $1$ as the root. Meanwhile, a color merge function $a \otimes b$ is given, satisfying that for $1 \le a, b \le k$, we have $1 \le a \otimes b \le k$. How many ways are there to color all nodes such that for any pair of nodes $u, v$ that have no ancestor relationship, the following holds: - The color of $\mathrm{LCA}(u, v)$ equals the merge of the color of node $u$ and the color of node $v$. Output the answer modulo $10^9 + 7$.

This problem contains multiple test cases. The first line contains a positive integer $t$ ($1 \le t \le 10^3$), the number of test cases. Then follow $t$ test cases, and for each test case: The first line contains two positive integers $n, k$. The next $k$ lines each contain $k$ positive integers. The $j$-th number in the $i$-th line is the value of $i \otimes j$. The next line contains $n - 1$ positive integers $f_2, f_3, \dots, f_n$, where $f_i$ is the parent of node $i$.

For each test case: Output one integer, representing the answer.

#### Explanation for Sample 1 The tree looks as follows:  Let $w_i$ be the weight of node $i$. Then there are the following $4$ assignment methods: - $w_i = \{1, 1, 1, 1, 1\}$; - $w_i = \{2, 2, 2, 1, 1\}$; - $w_i = \{2, 1, 1, 2, 2\}$; - $w_i = \{1, 2, 2, 2, 2\}$. #### Constraints and Notes **This problem uses bundled testdata.** For $100\%$ of the testdata, $1 \le n, \sum n \le 10^5$, $2 \le k \le 5$, and $1 \le f_i < i$. For $100\%$ of the testdata, $1 \le t \le 1000$. - Subtask 1 (5 pts): $n \le 5$; - Subtask 2 (11 pts): each node has at most $2$ children in the tree; - Subtask 3 (23 pts): each node has at most $3$ children in the tree; - Subtask 4 (13 pts): $k = 2$; - Subtask 5 (17 pts): $k \le 3$; - Subtask 6 (31 pts): no special constraints. Translated by ChatGPT 5