eolymp
Соревнования

USACO 2020 December

Спящие коровы

У фермера Джона есть n коров разных размеров. Первоначально он построил для каждой коровы индивидуальный хлев, но теперь некоторые коровы переросли свои хлевы. В частности, первоначально ФД построила n коровников размером t1, t2, ..., tn, в то время как коровы теперь имеют размер s1, s2,..., sn (1si, ti109).

Каждую ночь коровы проходят ритуал поиска хлева, чтобы спать. Корова i может спать в хлеву j тогда и только тогда, когда она помещаются в хлев (sitj). В каждом коровнике можно разместить не более одной коровы.

Будем говорить, что сопоставление коров с коровниками является максимальным тогда и только тогда, когда каждая корова, которой назначено стойло, может в нем поместиться, а каждая корова, которой не назначено стойло, не может поместиться ни в одном из пустых коровников.

Вычислить максимальное количество сопоставлений по модулю 109 + 7.

Входные данные

Первая строка содержит число n (1n3000). Вторая строка содержит n целых чисел s1, s2,..., sn. Третья строка содержит n целых чисел t1, t2, ..., tn.

Выходные данные

Выведите максимальное количество сопоставлений по модулю 109 + 7.

Пример

Вот список всех девяти максимальных соответствий. Упорядоченная пара (i, j) означает, что корове i назначен коровник 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)
Лимит времени 1 секунда
Лимит использования памяти 128 MiB
Входные данные #1
4
1 2 3 4
1 2 2 3
Выходные данные #1
9
Источник 2020 USACO Декабрь, Платина