Хоссам в попытках найти пиццу наткнулся на две перестановки \(a\) и \(b\) длины \(n\).
Вспомним, что перестановкой называется массив из \(n\) различных чисел от \(1\) до \(n\) в произвольном порядке. Например, \([2,3,1,5,4]\) — перестановка, а \([1,2,2]\) — не перестановка (\(2\) встречается дважды), и \([1,3,4]\) тоже не перестановка (\(n=3\), но в массиве есть число \(4\)).
Хоссам позабыл про пиццу и начал играть с этими перестановками. В процессе игры некоторые элементы первой перестановки смешались с элементами второй, но к удивлению Хоссама в итоге получилась тоже перестановка длины \(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\), удовлетворяющая всем ограничениям.
Выходные данные
Для каждого набора входных данных выведите количество различных перестановок \(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]\).
Примеры
| № | Входные данные | Выходные данные |
|
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
|
4
1
2
2
1
8
1
2
2
|