Farmer John có \(N\) con bò với nhiều kích thước khác nhau (\(1\le N\le 3000\)). Ban đầu ông xây một chuồng riêng phù hợp cho từng con, nhưng giờ một số con đã lớn quá cỡ chuồng. Cụ thể, FJ đã xây \(N\) chuồng có kích thước \(t_1,t_2,\ldots,t_N\), còn kích thước hiện tại của đàn bò là \(s_1,s_2,\ldots,s_N\) (\(1\le s_i,t_i\le 10^9\)).

Mỗi đêm, đàn bò thực hiện nghi thức tìm chuồng để ngủ. Bò \(i\) có thể ngủ trong chuồng \(j\) khi và chỉ khi nó vừa trong chuồng, tức \(s_i\le t_j\). Mỗi chuồng chứa nhiều nhất một con bò.

Ta gọi một cách ghép bò với chuồng là cực đại khi và chỉ khi mọi con bò được gán vào chuồng đều vừa với chuồng đó, đồng thời mọi con bò chưa được gán đều không thể vừa trong bất kỳ chuồng trống nào còn lại.

Hãy tính số cách ghép cực đại, lấy modulo \(10^9+7\).

Dữ liệu vào

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

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

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

Dữ liệu ra

In số cách ghép cực đại, lấy modulo \(10^9+7\).

Phân nhóm

• Trong các test 2-3, \(N\le 8\).
• Trong các test 4-12, \(N\le 50\).
• Trong các test 13-20, không có ràng buộc bổ sung.

Ví dụ

4
1 2 3 4
1 2 2 3

9

(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)

Nguồn

USACO 2020 December Contest, Platinum - Sleeping Cows: https://usaco.org/index.php?page=viewproblem2&cpid=1068

Tác giả: Nick Wu.