CF1670C Where is the Pizza?

在寻找披萨的过程中，小 Hosssam 遇到了两个长度为 $n$ 的排列 $a$ 和 $b$。 回忆一下，排列是一个包含 $n$ 个互不相同的整数的数组，这些整数从 $1$ 到 $n$，顺序任意。例如，$[2,3,1,5,4]$ 是一个排列，但 $[1,2,2]$ 不是排列（$2$ 在数组中出现了两次），$[1,3,4]$ 也不是排列（$n=3$，但数组中有 $4$）。 小 Hosssam 忘记了披萨，开始玩这两个排列。在玩耍的过程中，第一个排列中的一些元素和第二个排列中的一些元素混合在一起，令他惊讶的是，这些元素也组成了一个大小为 $n$ 的排列。 具体来说，他通过以下方式混合排列，形成了一个新数组 $c$： - 对于每个 $i$（$1\le i\le n$），他要么令 $c_i=a_i$，要么令 $c_i=b_i$。 - 数组 $c$ 是一个排列。 你知道排列 $a$、$b$，以及 $c$ 中某些位置的值。请计算有多少种不同的排列 $c$ 满足上述过程和已知的值。由于答案可能很大，请输出对 $10^9+7$ 取模的结果。 保证至少存在一个满足所有要求的排列 $c$。

第一行包含一个整数 $t$（$1 \le t \le 10^5$）——测试用例的数量。 每个测试用例的第一行包含一个整数 $n$（$1\le n\le 10^5$）——排列的长度。 接下来一行包含 $n$ 个互不相同的整数 $a_1,a_2,\ldots,a_n$（$1\le a_i\le n$）——第一个排列。 接下来一行包含 $n$ 个互不相同的整数 $b_1,b_2,\ldots,b_n$（$1\le b_i\le n$）——第二个排列。 接下来一行包含 $n$ 个整数 $d_1,d_2,\ldots,d_n$（$d_i$ 要么为 $0$，要么为 $a_i$，要么为 $b_i$）——已知的 $c$ 的部分值。如果 $d_i=0$，则 $c_i$ 没有要求。否则，要求 $c_i=d_i$。 保证至少存在一个满足所有要求的排列 $c$。 保证所有测试用例中 $n$ 的总和不超过 $5 \cdot 10^5$。

对于每个测试用例，输出满足条件的不同排列 $c$ 的数量，对 $10^9+7$ 取模。

在第一个测试用例中，可以通过该过程得到 $4$ 个不同的排列：$[2,3,1,4,5,6,7]$，$[2,3,1,7,6,5,4]$，$[2,3,1,4,6,5,7]$，$[2,3,1,7,5,6,4]$。 在第二个测试用例中，只能得到一个不同的排列：$[1]$。 在第三个测试用例中，可以得到 $2$ 个不同的排列：$[6,5,2,1,4,3]$，$[6,5,3,1,4,2]$。 在第四个测试用例中，可以得到 $2$ 个不同的排列：$[1,2,8,7,4,3,6,5]$，$[1,6,4,7,2,3,8,5]$。 在第五个测试用例中，只能得到一个不同的排列：$[1,9,2,3,4,10,8,6,7,5]$。 由 ChatGPT 4.1 翻译