Ngày nọ, buitrunghieu một cậu bé tinh nghịch và đáng yêu, sống ở một ngôi làng nằm giữa một cánh rừng rậm. Hiếu thường dạo chơi trong rừng và có một mối tình đặc biệt với những chú thỏ hoang dã.

Một ngày nọ, khi Hiếu đang đi lang thang trong rừng, cậu phát hiện ra rằng những chú thỏ mà cậu thường gặp đang gặp khó khăn. Những cái hang của chúng đã bị lũ động vật khác chiếm đoạt và chú thỏ không có nơi nào để ẩn náu.

Hiếu quyết định giúp đỡ các chú thỏ này. Có N \((1≤N≤3000)\) chú thỏ có kích thước khác nhau. Cụ thể, buitrunghieu đã giúp những chú thỏ ban đầu xây dựng N cái hang có kích thước là \(t_1, t_2, ..., t_N,\) do chúng đã ngày càng ăn nhiều cỏ hơn điều này làm kích thước của chúng thay đổi là thành \(s_1, s_2, ..., s_N (1≤s_i,t_i≤10^9)\).

Một con thỏ \(i\) có thể ngủ trong hang \(j\) nếu và chỉ nếu chúng vừa với hang đó \((s_i≤t_j)\). Mỗi hang chỉ có thể chứa tối đa một con thỏ.

buitrunghieu nói rằng một sự phù hợp của các con thỏ với các hang là nếu và chỉ nếu mỗi con thỏ được gán cho một cái hang có thể vừa với hang đó và nhưng con thỏ chưa được gán không thể vừa với bất kỳ hang trống nào trong số các hang không được gán.

Tính số lượng phù hợp, kết quả có thể rất lớn nên hãy mod \(10^9+7\).

INPUT FORMAT

Dòng đầu tiên chứa N.

Dòng thứ hai chứa N số nguyên cách nhau bởi dấu cách là \(s_1, s_2, ..., s_N\).

Dòng thứ ba chứa N số nguyên cách nhau bởi dấu cách là \(t_1, t_2, ..., t_N,\).

OUTPUT FORMAT

Số lượng phù hợp mod \(10^9+7\)

SUBTEST

\(N <= 8\) chiếm \(15\%\) số điểm.

\(N <= 50\) chiếm \(45\%\) số điểm.

\(50\%\) test còn lại không có ràng buộc bổ sung.

Ví dụ:

Input

4
1 2 3 4
1 2 2 3

Ouput

9

Dưới đây là danh sách của tất cả các sự phù hợp a. Một cặp (i, j) có nghĩa là con thỏ i được gán vào hang j.

(1, 1), (2, 2), (3, 4)

(1, 1), (2, 3), (3, 4)

(1, 1), (2, 4)

(1, 2), (2, 3), (3, 4)

(1, 2), (2, 4)

(1, 3), (2, 2), (3, 4)

(1, 3), (2, 4)

(1, 4), (2, 2)

(1, 4), (2, 3)