信赖跃迁：置换轨迹计算

Problem Description

在这个世界里，信赖决定了一个人能否成为英雄，每个人的信赖值会被记录在手腕上的表盘上，反映个人的能力和影响力。 潇月卿，原本只是一位普通的生活博主，拥有平凡但充实的日常。随着她在网络上的影响力不断增加，越来越多的人愿意将自己的信赖交给她。她的信赖值急剧上升，最终获得了强大的空间转移能力。她能够瞬间穿越不同的时空，带领她的粉丝探索世界的奇迹与未知。然而，信赖值并非一成不变，它随着人们的情感波动和需求不断变化。潇月卿的力量，也因此变得不稳定。 某次跃迁中，潇月卿遭遇了跃迁引擎故障，时空通道发生了断裂。为了恢复通道的稳定性，她需要解决一个复杂的置换问题。这不仅与信赖值的变化有关，还涉及到空间跃迁的多项式运算。潇月卿必须通过一系列置换和幂次运算，来计算通向目标置换 $q$ 的跃迁路径，并验证所有可能性，以修复时空裂缝。 作为这场时空冒险的关键，潇月卿需要你的帮助。给定一个长度为 $n$ 的置换 $q$ 和一个长度为 $m$ 的整数序列 $k_1, k_2, \ldots, k_m$，你需要计算有多少个长度为 $m+1$ 的置换序列 $p_0, p_1, \ldots, p_m$ 能够满足以下关系：

$$p_0 \circ p_1^{k_1} \circ p_2^{k_2} \circ \ldots \circ p_m^{k_m} = q $$

其中，$\circ$ 表示置换的复合运算，$p_i$ 表示一个长度为 $n$ 的置换。 这一问题的解答，将直接决定时空通道是否能够恢复，潇月卿的英雄之路是否能继续。在这场充满未知与挑战的时空冒险中，能否成功跨越这道难题，就交给你了。

Input

第一行包含一个整数 $t$（$1\le t\le 10$），表示数据组数，每组数据输入如下： 第一行包含两个整数 $n$（$1\le n\le 10^5$）和 $m$（$1 \le m \le 10^5$），表示置换 $q$ 的长度和序列 $k$ 的长度。 第二行包含 $n$ 个整数 $q_0, q_1,\ldots, q_{n-1}$，表示置换 $q$。保证 $q$ 是一个有效的置换，即每个元素都不重复且在 $[0, n-1]$ 之间。 第三行包含 $m$ 个整数 $k_1,\ldots , k_{m}$（$1 \le k_i \le 10^5$），表示序列 $k$。

Output

对于每组数据，输出一行一个整数，表示满足条件的置换序列 $p$ 的个数。由于答案可能非常大，请输出答案对 $10^9+7$ 取模的结果。

Sample Input

3
2 1
1 0
3
2 1
1 0
3
1 1
0
1

Sample Output

2
2
1

Hint

对于第一个样例，满足条件的两种 $\{p_0,p_1\}$ 分别为 $\{\{1,0\},\{0,1\}\}$ 和 $\{\{0,1\},\{1,0\}\}$。 本节主要介绍相关数学背景。 置换是一种对序列进行的运算。一个长度为 $n$ 的置换是一个 $0 \sim n-1$ 的排列 $P_0, P_1, \ldots, P_{n-1}$，表示将原序列下标为 $i$ 的元素替换成原序列下标为 $P_i$ 的元素（下标从 $0$ 开始）。例如，对原序列 $[2,4,0,3,1]$ 进行置换运算 $P=[2,0,4,3,1]$ 之后得到的序列为 $[0,2,1,3,4]$。 对于两个置换 $P$ 和 $Q$，其复合运算 $P \circ Q$ 表示对置换 $P$ 做置换 $Q$ 之后得到的结果。 置换的幂运算 $P^k$（$k \ge 1$）表示为对置换 $P$ 复合 $k-1$ 次自己，即 $P^k = \underbrace{P \circ \ldots \circ P}_{k\text{ 个 }P}$。

Source

2025“钉耙编程”中国大学生算法设计暑期联赛（5）