Tàu Vũ Trụ

Có $N$ con bò với kích thước $s_1,s_2,\dots ,s_N$ và $N$ chuồng với kích thước $t_1,t_2,\dots ,t_N$. Con bò $i$ có thể vào chuồng $j$ nếu $s_i\le t_j$. Mỗi chuồng chứa tối đa một con bò.

Một ghép cặp tối đại (maximal matching) là một tập hợp các cặp (bò, chuồng) thoả mãn:

• Mỗi con bò và mỗi chuồng xuất hiện trong tối đa một cặp.
• Mỗi cặp (bò $i$, chuồng $j$) phải có $s_i\le t_j$.
• Mọi con bò chưa được ghép đều không vừa bất kỳ chuồng trống nào (tức là không tồn tại chuồng $j$ trống nào có $s_i\le t_j$).

Đếm số ghép cặp tối đại khác nhau modulo ${10}^9+7$.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên $N$.
• Dòng thứ hai chứa $N$ số nguyên $s_1,s_2,\dots ,s_N$ — kích thước các con bò.
• Dòng thứ ba chứa $N$ số nguyên $t_1,t_2,\dots ,t_N$ — kích thước các chuồng.

Dữ liệu ra

In ra một số nguyên duy nhất — số ghép cặp tối đại modulo ${10}^9+7$.

Ràng buộc

• $1\le N\le 3000$
• $1\le s_i,t_j\le {10}^9$

Ví dụ

Ghi chú

Hai ghép cặp được coi là khác nhau nếu tồn tại ít nhất một cặp (bò, chuồng) thuộc ghép cặp này mà không thuộc ghép cặp kia.