← 返回题目列表

Codeforces · 1670/C

C. 披萨在哪里?

中文机器翻译题面 查看原题

在寻找披萨时,小 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$$$。

示例

输入 #1

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

输出 #1

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]$$$。