题目描述

在寻找披萨的过程中，小 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$——测试用例的数量。

每个测试用例的第一行包含一个整数 $n$——排列的长度。

接下来一行包含 $n$ 个互不相同的整数 $a_1,a_2,\ldots,a_n$——第一个排列。

接下来一行包含 $n$ 个互不相同的整数 $b_1,b_2,\ldots,b_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$。

输出格式

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

9
7
1 2 3 4 5 6 7
2 3 1 7 6 5 4
2 0 1 0 0 0 0
1
1
1
0
6
1 5 2 4 6 3
6 5 3 1 4 2
6 0 0 0 0 0
8
1 6 4 7 2 3 8 5
3 2 8 1 4 5 6 7
1 0 0 7 0 3 0 5
10
1 8 6 2 4 7 9 3 10 5
1 9 2 3 4 10 8 6 7 5
1 9 2 3 4 10 8 6 7 5
7
1 2 3 4 5 6 7
2 3 1 7 6 5 4
0 0 0 0 0 0 0
5
1 2 3 4 5
1 2 3 4 5
0 0 0 0 0
5
1 2 3 4 5
1 2 3 5 4
0 0 0 0 0
3
1 2 3
3 1 2
0 0 0

4
1
2
2
1
8
1
2
2

说明 / 提示

在第一个测试用例中，可以通过该过程得到 $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 翻译

1
1
1
1
0

1

1
2
2 1
1 2
0 0

2

数据范围

保证所有测试用例中 $n$ 的总和不超过 $5 \cdot 10^5$。

（$1 \le t \le 10^5$）

（$1\le n\le 10^5$）

（$1\le a_i\le n$）

（$1\le b_i\le n$）