Cho bảng kích thước 2xn , mỗi dòng của bảng là hoán vị độ dài n chứa các
số 1,2,3,...,n, các số cùng một cột thì khác nhau.
Một bảng là đẹp nếu không có số nào cùng hàng bằng nhau và không có số nào
cùng cột bằng nhau.
Bạn có thể làm thao tác sau vô số lần: chọn 2 ô cùng cột và hoán đổi giá
trị của 2 ô đó.
Đếm số bảng đẹp có thể tạo thành, vì kết quả có thể lớn nên in ra kết quả
mod 1000000007.
Input:
Dòng đầu chứa số nguyên n(2<=n<=10^5).
Hai dòng tiếp theo chứa các số của bảng, mỗi dòng là 1 hoán vị của n số
1,2,3,...,n, không có 2 ô nào cùng cột chứa giá trị giống nhau.
Output:
In ra kết quả mod 1000000007.
input | output |
4
1 4 2 3
3 2 1 4
|
2
|
input | output |
8
2 6 5 1 4 3 7 8
3 8 7 5 1 2 4 6
|
8
|