У Фермера Джона есть \(N\) \((1 \le N \le 3000)\) коров различных размеров.
Изначально он построил для каждой коровы персональный амбар, но сейчас некоторые из коров
переросли свои амбары. Точнее, ФД изначально построил \(N\) амбаров с размерами
\(t_1,t_2,\ldots,t_N\),
а коровы сейчас имеют размеры
\(s_1,s_2,\ldots,s_N\)
(\(1\le s_i,t_i\le 10^9\)).
Каждую ночь коровы ищут амбар для ночевки. Корова \(i\) может спать в амбаре \(j\)
если и только если, она помещается в амбар, то есть (\(s_i\le t_j\)).
В каждом амбаре может ночевать только одна корова.
Мы говорим, что соответствие коров амбарам максимально если и только если
корова, назначенная амбару, помещается в него, и каждая из не назначенных коров
не помещается ни в один из оставшихся свободными амбаров.
Вычислите количество максимальных соответствий по модулю \(10^9 + 7\).
ФОРМАТ ВВОДА (с клавиатуры / stdin):
Первая строка содержит
\(N\).
Вторая строка содержит \(N\) разделённых пробелами целых чисел \(s_1,s_2,\ldots,s_N\).
Третья строка содержит \(N\) разделённых пробелами целых чисел \(t_1,t_2,\ldots,t_N\).
ФОРМАТ ВЫВОДА (на экран / stdout):
Количество максимальных соответствий по модулю \(10^9 + 7\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
1 2 3 4
1 2 2 3
|
9
|