Trên mỗi hàng của bảng ô vuông ~2 \times n~, có điền một hoán vị nào đó của các số ~(1,2,...,n)~. Ta được thực hiện các thao tác có dạng: chọn một cột nào đó và đổi chỗ hai số (dưới lên trên và trên xuống dưới). Ta gọi một cấu hình thu được từ bảng ban đầu là đẹp nếu như không có hai số nào trên cùng một hàng là giống nhau. Đếm số cấu hình khác nhau có thể thu được.

Input

Dòng đầu tiên gồm số nguyên dương ~n~ với ~1 \le n \le 10^5.~

Trong hai dòng tiếp theo, mỗi dòng cho một hoán vị của các số ~1 \to n~.

Output

Kết quả của bài toán, do số có thể rất lớn nên lấy mod ~10^9+7.~

Sample input 1

4
1 4 2 3
3 2 1 4

Sample output 1

2

Sample input 2

3
1 2 3
1 2 3

Sample output 2

1

Giải thích

Trong VD 1, ta thấy rằng có hai cấu hình là ~(1,4,2,3)~ ở hàng trên còn ~(3,2,1,4)~ ở hàng dưới; hoặc ngược lại. Còn ở VD 2, ta thấy mọi cách đổi thì bảng đều giữ nguyên như cũ.