Codeforces Round 788 (Div. 2) |
---|
Закончено |
Хоссам в попытках найти пиццу наткнулся на две перестановки $$$a$$$ и $$$b$$$ длины $$$n$$$.
Вспомним, что перестановкой называется массив из $$$n$$$ различных чисел от $$$1$$$ до $$$n$$$ в произвольном порядке. Например, $$$[2,3,1,5,4]$$$ — перестановка, а $$$[1,2,2]$$$ — не перестановка ($$$2$$$ встречается дважды), и $$$[1,3,4]$$$ тоже не перестановка ($$$n=3$$$, но в массиве есть число $$$4$$$).
Хоссам позабыл про пиццу и начал играть с этими перестановками. В процессе игры некоторые элементы первой перестановки смешались с элементами второй, но к удивлению Хоссама в итоге получилась тоже перестановка длины $$$n$$$.
Более конкретно, он смешал перестановки, получив массив $$$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$$$.
971 2 3 4 5 6 72 3 1 7 6 5 42 0 1 0 0 0 0111061 5 2 4 6 36 5 3 1 4 26 0 0 0 0 081 6 4 7 2 3 8 53 2 8 1 4 5 6 71 0 0 7 0 3 0 5101 8 6 2 4 7 9 3 10 51 9 2 3 4 10 8 6 7 51 9 2 3 4 10 8 6 7 571 2 3 4 5 6 72 3 1 7 6 5 40 0 0 0 0 0 051 2 3 4 51 2 3 4 50 0 0 0 051 2 3 4 51 2 3 5 40 0 0 0 031 2 33 1 20 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]$$$.
Название |
---|