### 问题描述 大衣有一个长度为 $N$ 的排列 $P$，一个长度为 $N$ 的数组 $A$ 和一个整数 $M​$。 最初，$0\le A_i\le M$，然后将数组 $A$ 中的所有的元素 $0$ 用不大于 $M$ 的正整数替代得到数组 $A'$。 数组 $A'$ 将进行 $N$ 次操作： - 在第 $i​$ 次操作，将 $A_i'​$ 修改为 $A_{P_i}'​$。 如果在 $N$ 次操作后数组 $A'​$ 的所有元素相同，我们称该数组是美丽的。 请找出美丽的数组 $A'​$ 的数量，答案可能很大，将其对 $10^9+7​$ 取模。 ### 输入格式 第一行输入一个正整数 $T$ 表示测试数据的组数。 接下来 $T$ 组测试数据每组输入三行： - 第一行输入两个整数 $N,M$ 分别表示排列和数组的长度，数组元素的上界。 - 第二行输入 $N​$ 个整数 $P_1,P_2,\cdots,P_N​$ 表示排列 $P​$。 - 第三行输入 $N$ 个整数 $A_1,A_2,\cdots,A_N$ 表示数组 $A$。 ### 输出格式 对于每组测试数据，输出一个整数表示美丽的数组 $A'​$ 的数量，答案可能很大，将其对 $10^9+7​$ 取模，并换行。 ### 样例输入1 ```text 3 4 3 2 1 4 3 0 2 0 2 3 2 3 1 2 0 0 0 8 54 8 1 2 4 3 6 7 5 0 0 0 0 0 0 0 0 ``` ### 样例输出1 ```text 9 8 459165024 ``` ### 说明 样例 $1​$：排列 $P=[2,1,4,3]​$，一个可能的美丽的数组为 $A'=[1,2,3,2]​$，它将进行以下操作： - 在第 $1$ 次操作，$A_1'$ 被修改为 $A_{P_1}'=A_2'=2$，现在的数组 $A'$ 变为 $[2,2,3,2]$。 - 在第 $2​$ 次操作，$A_2'​$ 被修改为 $A_{P_2}'=A_1'=2​$，现在的数组 $A'​$ 变为 $[2,2,3,2]​$。 - 在第 $3$ 次操作，$A_3'$ 被修改为 $A_{P_3}'=A_4'=2$，现在的数组 $A'$ 变为 $[2,2,2,2]​$。 - 在第 $4$ 次操作，$A_4'$ 被修改为 $A_{P_4}'=A_3'=2$，现在的数组 $A'$ 变为 $[2,2,2,2]$。 除此以外其他可能的美丽的数组 $A'$ 有：$[1,2,1,2]$，$[1,2,2,2]$，$[2,2,1,2]$，$[2,2,2,2]$，$[2,2,3,2]$，$[3,2,1,2]$，$[3,2,2,2]$，$[3,2,3,2]$，所以美丽的数组 $A'$ 一共有 $9$ 个。 ### 评测数据规模 对于所有的评测数据，$1\le T\le 20$，$1\le N\le 10^4$，$1\le M\le 10^9$，$0\le A_i\le M$。