题目描述

有一棵 $n$（$1\le n\le 10^5$）个点的树以及 $k$（$2\le k\le 5$）个颜色，根节点为 $1$。同时，给定一个颜色合并函数 $a\otimes b$，满足当 $1\le a,b\le k$，有 $1\le a\otimes b\le k$。

请问有多少个方案对所有点染色，使得当点对 $u,v$ 之间没有祖先关系，有：

• $u$ 和 $v$ 最近公共祖先的颜色为点 $u$ 的颜色和点 $v$ 的颜色之并。

答案对 $10^9+7$ 取模。

输入格式

本题有多组数据，第一行一个正整数 $t$（$1\le t\le 10^3$），为数据组数。接下来 $t$ 组数据，其中对于每一组数据：

第一行两个正整数 $n,k$。

接下来 $k$ 行，每行 $k$ 个正整数。第 $i$ 行第 $j$ 个数为 $i\otimes j$ 的值。

接下来 $n-1$ 个正整数 $f_2,f_3,\dots,f_n$，其中 $f_i$ 是 $i$ 的父亲节点。

输出格式

对于每一组数据：

输出一个整数，表示答案。

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

4
2

提示

样例 1 解释

树的形态如下：

设 $w_i$ 为第 $i$ 个点的点权，则有如下 $4$ 种分配方式：

• $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\}$。

数据规模与约定

本题采用捆绑测试。

对于 $100\%$ 的数据，$1\le n,\sum n\le10^5$，$2\le k\le 5$，$1\le f_i<i$。

对于 $100\%$ 的数据，$1\le t\le 1000$。

• Subtask 1（5 pts）：$n\le5$；
• Subtask 2（11 pts）：树上任何节点孩子个数至多为 $2$；
• Subtask 3（23 pts）：树上任何节点孩子个数至多为 $3$；
• Subtask 4（13 pts）：$k=2$；
• Subtask 5（17 pts）：$k\le3$；
• Subtask 6（31 pts）：无特殊限制。