Description

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$.

Input Format

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$.

Output Format

For each test case:

Output one integer, representing the answer.

2
5 2
1 2
2 1
1 2 1 4
5 2
1 2
1 1
1 2 1 4

4
2

Hint

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