Cho hai dãy số nguyên dương độ dài \(n\): \(a = (a_1, a_2, \dots, a_n)\) và \(b = (b_1, b_2, \dots, b_n)\). Biết rằng các phần tử của hai dãy số là các số nguyên dương, không nhất thiết là phân biệt, được lấy từ tập \(\{1, 2, \dots, n\}\). Đối với hai dãy đã cho ta có thể thực hiện phép biến đổi sau đây: Chọn hai chỉ số \(i\) và \(j\) với \(1 \leq i \leq j \leq n\), sau đó hoán đổi hai dãy con \(a_i, a_{i+1}, \dots, a_j\) và \(b_i, b_{i+1}, \dots, b_j\) của hai dãy cho nhau ta thu được hai dãy mới:

và

Như vậy, phép biến đổi nêu trên được xác định bởi cặp hai chỉ số \((i, j)\).

Nếu như sau khi thực hiện phép biến đổi có ít nhất một trong hai dãy thu được là hoán vị của \(\{1, 2, \dots, n\}\), thì ta thu được một hoán vị trộn.

Yêu cầu: Hãy xác định xem có thể thu được hoán vị trộn bởi bao nhiêu cách.

Input

• Dòng đầu tiên chứa số nguyên \(n\) (\(1 \leq n \leq 10^4\)).
• Dòng thứ hai chứa dãy số \(a_1, a_2, \dots, a_n\).
• Dòng thứ ba chứa dãy số \(b_1, b_2, \dots, b_n\).
• Các số trên cùng dòng được ghi cách nhau bởi dấu cách.

Output

• Ghi ra một số nguyên duy nhất là số cách khác nhau có thể thu được hoán vị trộn bằng cách thực hiện phép biến đổi đã nêu đối với hai dãy đã cho.

Example

6
3 2 1 4 4 5
2 3 3 4 6 5

8

2
1 2
1 2

3

Scoring

• Subtask \(1\) (\(40\%\) số điểm): \(n \leq 100\).
• Subtask \(2\) (\(60\%\) số điểm): Không có ràng buộc gì thêm.