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